1.前言

从“快慢”到“对撞”

如果说快慢指针（26、27题）是在数组上“加工零件”，那么对撞双指针（15、11题）就是在搜索空间里“围追堵截”。它们的本质都是利用数据的特性（有序性或单调性），剔除掉无效的计算路径。

2. 15. 三数之和

2.1分析

首先看到整数数组nums,判断是否存在三元数组,这道题我刚开始的想法就是像之前的滑动窗口一样去便利,但是这样的话时间复杂度就会是O(N^3)需要遍历很多次就会超时.并且需要补充一点的是滑动窗口本质上是一个伸缩的“窗帘”。它处理的对象必须是连续的子数组（Subarray）或连续的子串（Substring）。

那么我就在考虑去使用双指针去做这道题,首先我们就可以排序sort(),这样也可以为后面的去重做铺垫. 我们就可以i遍历for循环,用left指针和right指针进行操作,并且和大往左走，和小往右走,

那接下来看我的画图演示:

这道题有个很关键的难点就是如何去重?

举个例子:

• 外层去重: 数组：[-1, -1, 0, 1, 2],第一轮 i = -1 时, 双指针帮你找到的数组是(-1,0,1), 到第二轮时, i 还是等于 -1 找到的数组肯定与刚才那个相同, 所以我们就需要去重.  nums[i] == nums[i-1]，直接 continue（跳过），这就是外层去重。
• 内层去重: 注意: 只有当你找到了一组 sum == 0 的答案后，才需要执行这一步。假设固定了 nums[i] = -2，剩下的数组是 [1, 1, 1, 1, 1, 1]。left 指向1 , right指向1 , 找到数组(-2,1,1), 但是下一轮你的left还是1, 就会重复(-2,1,1)!

2.2 上代码

//15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>>res=new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //外层的i去重
            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[left]==nums[left+1]){
                        left++;
                    }
                    //右边去重
                    while (left<right && nums[right]==nums[right-1]){
                        right--;
                    }
                    //找到一组答案后，左右一起收缩
                    left++;
                    right--;
                } else if (sum<0) {
                    left++;
                }else{
                    right--;
                }
            }

        }
        return res;
    }

3. 11. 盛最多水的容器

这道题的代码极短，但背后的贪心策略极深。

3.1 思路

这道题的意思是算面积最大,那么我们可以根据题意写出如下公式:

area=(R-L)*Math.min(height[L],hight[R]);

接下来就需要把最大面积更新max

然后本题的重难点来了,我们需要怎么移动L和R指针呢?

核心思想: 谁矮谁移动

L矮的话就L++,R矮的话就R--, 这样我们就可以找最大的啦

3.2 代码

这道题比较简单稍加思考就能相=想出,我就不画图啦,直接上代码:

//11.盛最多水的容器
    public int maxArea(int[] height) {
        int left=0;
        int right= height.length-1;
        int res=0;
        while (left<right){
            //计算出面积
            int area=(right-left)*Math.min(height[right], height[left]);
            res=Math.max(res,area);
            //谁矮谁移动
            if (height[left]<height[right]){
                left++;
            }else{
                right--;
            }

        }
        return res;
    }

4. 总结

双指针的灵魂

双指针不仅仅是两个 int 变量，它是 “剪枝” 思想的体现。

• 在 15 题中，我们剪掉了那些会导致重复的路径。

• 在 11 题中，我们剪掉了那些“移动长板必减面积”的无效路径。