# 11. Container with the most water

Give you n nonnegative integers a1, a2,..., an, each representing a point (i, ai) in the coordinate. Draw n vertical lines in the coordinates. The two endpoints of vertical line i are (i, ai) and (i, 0). Find two of these lines so that the container they form with the x-axis can hold the most water.

My idea:
Double pointers m, N, m from front to back, n from back to front. The width n-m must be smaller and smaller, so we only need to judge whether the height increases. If not, it must not exceed the previous volume.
Execution time: 5 ms, beating 43.66% of users in all Java submissions
Memory consumption: 51.8 MB, beating 33.11% of users in all Java submissions

```class Solution {
public int maxArea(int[] height) {
int result =(height.length-1)*Math.min(height[0],height[height.length-1]);
int m=0,n=height.length-1;
while(m<n){
if(height[m]>height[n]){
n--;
if(height[n]<=height[n+1]){
continue;
}
}else{
m++;
if(height[m]<=height[m-1]){
continue;
}
}
int s = (n-m)*Math.min(height[m],height[n]);
if(s>result){
result = s;
}

}
return result;
}
}
```

Reference writing: ternary
Every time we move the short board inward, all the elimination States will not lead to the loss of the maximum area
Execution time: 4 ms, beating 76.25% of users in all Java submissions
Memory consumption: 52.1 MB, beating 7.67% of users in all Java submissions

```class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while(i < j){
res = height[i] < height[j] ?
Math.max(res, (j - i) * height[i++]):
Math.max(res, (j - i) * height[j--]);
}
return res;
}
}
```

# 15. Sum of three

Give you an array num containing n integers. Judge whether there are three elements a, b and c in num, so that a + b + c = 0? Please find all triples with sum 0 and no repetition.
Note: the answer cannot contain duplicate triples.

My idea:
Three level cycle, violent problem solving. But there is no way to remove the weight.

```class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums.length<3){
return result;
}
for(int i = 0;i<nums.length;i++){
for(int j = i+1;j<nums.length;j++){
for(int k = j+1;k<nums.length;k++){
if(nums[i]+nums[j]+nums[k]==0&&nums[i]!=nums[k]&&nums[j]!=nums[k]){
List<Integer> ans = new ArrayList<Integer>();
}
}
}
}
return result;
}
}
```

Reference ideas:
1. The enumerated ternary array abc satisfies a < = B < = C, ensuring [a,b,c], rather than [b,a,c];
2. In a triple loop, adjacent enumeration elements cannot be repeated
3. Optimize the triple cycle, a + B + c = 0, when B increases, c must decrease, and B and c constitute double pointers.

My improvement Code:
Execution time: 25 ms, beating 57.76% of users in all Java submissions
Memory consumption: 42.6 MB, beating 38.77% of users in all Java submissions

```class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
int length = nums.length;
Arrays.sort(nums);
for (int i = 0; i < length - 2; i++) {
int a = i + 1;
int b = length - 1;
//duplicate removal
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while (a < b) {
int sum = nums[i] + nums[a] + nums[b];
if (sum == 0) {
List<Integer> list = new ArrayList<Integer>();
a++;
b--;
//nums[i] and nums[a] are the same. nums[b] must be unique and de duplication
while(a<b&&nums[a]==nums[a-1]){
a++;
}
while(b>a&&nums[b]==nums[b+1]){
b--;
}
} else if (sum > 0) {
b--;
} else if (sum < 0) {
a++;
}
}
}
return result;
}
}
```

Optimization:
Execution time: 22 ms
Memory consumption: 42.3 MB

```class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
int length = nums.length;
Arrays.sort(nums);
//Because of the sorting rule, I is the minimum value, and there must be nums [i] < = 0 to meet nums[i] + nums[a] + nums[b] = 0;
for (int i = 0; i < length - 2 && nums[i] <= 0; i++) {
int a = i + 1;
int b = length - 1;
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while (a < b) {
int sum = nums[i] + nums[a] + nums[b];
//Judge most cases first to reduce the cost
if (sum > 0) {
b--;
} else if (sum < 0) {
a++;
}else if (sum == 0) {
List<Integer> list = new ArrayList<Integer>();
//Before the double pointer changes, skip the duplicate items before moving
while(a<b&&nums[a]==nums[a+1]){
a++;
}
while(b>a&&nums[b]==nums[b-1]){
b--;
}
a++;
b--;
}
}
}
return result;
}
}
```

Keywords: Algorithm Interview

Added by AAFDesign on Tue, 08 Mar 2022 15:39:39 +0200