移动零

如何控制双指针呢？

1. [左指针，右指针)这里必须全为0

2. 交换了后左指针往后移一位，右指针找下一个不为0的位置（保证1的成立），右指针到数组尾部结束

3. 在遇到第一个0之前，左右指针指向同一个位置，所以交换了和没交换一样 遇到第一个0后，就开始了[左指针，右指针），只要一直保持他即可

错误写法：

想想为啥报出数组越界，为啥下面没有报数组越界

总结：每次left++或right++后，需要立刻进行判断，所以把++放在最后

 class Solution {
     public void moveZeroes(int[] nums) {
         int left = 0;
         int right = 0;
         while (right < nums.length){
             //关键在这里，出问题的就是这里
             //这个案例:[1,2,0,3,4,0,0]
             //在[1,2,3,4,0,0,0],这时left=4，right=5。
             //之后right++直到right=7，数组越界了但是这里跳到下面去进行交换，就会导致数组越界
             while (right < nums.length && nums[right]==0)right++;
             int tmp = nums[left];
             nums[left] = nums[right];
             nums[right] = tmp;
             left++;
             right++;
         }
     }
 }

这下面是两个相同逻辑但不同写法

 class Solution {
     public void moveZeroes(int[] nums) {
         int left = 0;
         int right = 0;
         while (right < nums.length){
             if(nums[right] != 0){
                 int tmp = nums[left];
                 nums[left] = nums[right];
                 nums[right] = tmp;
                 left++;
             }
             right++;
         }
     }
 }

 class Solution {
     public void moveZeroes(int[] nums) {
         int left = 0;
         for(int right = 0;right < nums.length;right++){//到数组尾部结束
             if (nums[right] == 0)continue;//找下一个不为0的位置
             int tmp = nums[left];
             nums[left] = nums[right];
             nums[right] = tmp;
             left++;//交换完后++
         }
     }
 }

盛水最多的容器

思路对了就很简单

1. 初始一头一尾

2. 每次移动小的那个（因为如果移动大的话，不会增加，移动小弟反而有可能）

 class Solution {
     public int maxArea(int[] height) {
         int max = Integer.MIN_VALUE;
         int left = 0;
         int right = height.length-1;
         while (left < right){
             int a = Math.min(height[left],height[right]);
             int b = right-left;
             max = Math.max(max,a*b);
             if(height[left] < height[right]){
                 left++;
             }else {
                 right--;
             }
         }
         return max;
     }
 }

三数之和

要求：

• sum=0

• i，j，k三者互不相对

• （num[i],num[j],nums[k]）不可以重复

1. 首先对数组进行排序

2. 如果 nums[i]大于 0，则三数之和必然无法等于 0，break

3. 如果 nums[i] == nums[i−1]，则说明该数字已经算过了，会导致结果重复，continue

4. 再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集

5. 当 sum 0 时，nums[L] nums[L+1] 则会导致结果重复，应该跳过，L++

6. 当 sum 0 时，nums[R] nums[R−1] 则会导致结果重复，应该跳过，R−−

7. sum!=0时怎么移动L和R

 class Solution {
     List<List<Integer>> res = new LinkedList<>();
     public List<List<Integer>> threeSum(int[] nums) {
         Arrays.sort(nums);
         for(int i = 0;i < nums.length;i++){
             if(nums[i] > 0)break;
             //对过去值进行判断，防止重复
             if(i>0 && nums[i]==nums[i-1])continue;
             int left = i+1;
             int right = nums.length-1;
             while (left < right){
                 int sum = nums[i]+nums[left]+nums[right];
                 if(sum==0){
                     //先添加结果再跳过未来重复值
                     //res.add
                     //while(nums[left]==nums[left-1])
                     //while(nums[right]==nums[right+1])
                     //可是这两个都是已经添加进结果了，比较有毛用啊，应该一个是已经添加的，一个是未添加的
                     res.add(Arrays.asList(nums[i],nums[left],nums[right]));
                     while (left<right&&nums[left]==nums[left+1])left++;
                     while (left<right&&nums[right]==nums[right-1])right--;
                     left++;
                     right--;
                 }else if(sum < 0){
                     left++;
                 }else if(sum > 0){
                     right--;
                 }
 ​
             }
         }
         return res;
     }
 }