11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

解法：双指针

采用左右指针，左指针从下标0开始，右指针从下标heigth.length-1开始。、

每次计算左右两条线与x轴构成的容器的面积。更新最大面积。

如何移动左右指针？

• 如果 height[left] <= height[right]：
  说明左边的线更矮（或者一样高），高度被左边限制。
  不管你怎么往里移动右边的指针，宽度会变小，高度最多还是 height[left]，很难变大。
  所以我们尝试去换掉矮的那根：移动左指针 left++，去看看能不能找到更高的线，从而有机会组成更大的面积。

• 否则（height[left] > height[right]）：
  右边那根线更矮，高度被右边限制，同理，我们移动右指针 right--，去尝试找一根更高的右边线。

• 每一步都丢弃当前较矮的那一边，因为它是“短板”，
  保留较高的一边，指望遇到更高的那一根，从而可能得到更大的面积。

循环何时结束？

当left >= right时，左右指针相遇，所有情况都已经考虑，循环结束。

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

总结

1. 确定双指针。

2. 确定指针移动规则。

3. 确定循环退出条件。

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解法： 双指针

这道题需要三个数，可以先确定一个数，在这个数右边利用双指针法寻找另外两个数，使三数之和相加为0。其中需要注意去重。

1. 排序。对数组进行排序，排序能做到快速跳过重复数字，双指针可以单调性移动。

2. 固定一个数nums[i]。设left = i+ 1， right = nums.length - 1;，移动left和right，寻找三数之和为0的组合，加入数组中。

3. 去重。当i > 0 && nums[i] == nums[i - 1]时，nums[i-1]已经计算过，此时要进行去重。同理

while(left < right && nums[right] == nums[right - 1]) right--;

 while(left < right && nums[left] == nums[left + 1]) left++;

也需要去重。

4. 剪枝。当第一个数nums[[i]>0，数组升序排序，说明，无论如何三个数相加都不可能为0了，则直接退出循环。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        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(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(left < right && nums[right] == nums[right - 1]) right--;
                    while(left < right && nums[left] == nums[left + 1]) left++;
                    left++;
                    right--;
                }else if(sum < 0){
                    left++;
                }else{
                    right--;
                }
            }
        }
        return res;
    }
}