双指针

🎯 LeetCode Hot 100

---

1. 移动零

难度：简单 | LeetCode 链接

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

思路

用双指针，分别寻找非0和0元素，交换位置。

代码

class Solution {
    public void moveZeroes(int[] nums) {
        int length = nums.length;
        //双指针
        for(int left=0;left<length;left++){
            //左指针寻找0
            if(nums[left] == 0){
                int right = left+1;

                //右指针找到非0数，交换位置
                while(right<length&&nums[right]==0){
                    right++;
                }
                //防止right越界
                if(right>=length){
                    return;
                }
                int tmp = nums[right];
                nums[right] = nums[left];
                nums[left] = tmp;
            }
        }
    }
}

复杂度：时间 O(n)，空间 O(1)

---

2. 盛最多水的容器

难度：中等 | LeetCode 链接

给定 n 个非负整数 height，每个数代表坐标中的一个点 (i, height[i])。找出两条线，使得它们与 x 轴构成的容器可以容纳最多的水。

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
解释：选择 height[1]=8 和 height[8]=7，宽度为 7，面积 = 7 × 7 = 49

思路

双指针从两端向中间收缩，每次移动较短的那条边。

为什么移动短边？

• 面积 = min(左高, 右高) × 宽度
• 宽度一定减小，要想面积可能变大，只能让高度变大
• 移动长边：min 值不变或变小，面积一定变小
• 移动短边：min 值可能变大，面积可能变大
• 从图中可以看到，利用空间缩减的思想：移动短边并不会漏掉最优解，目的是可以跳过一些不必要的计算。
• 详解见LeetCode

代码

class Solution {
    public int maxArea(int[] height) {
        //使用双指针
        int l = 0,r = height.length-1;
        int res = 0;
        //比较l和r，移动height小的指针
        while(l<r){
            //计算面积
            int area = (r-l)*Math.min(height[l],height[r]);
            res = Math.max(res,area);
            //继续寻找
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return res;
    }
}

复杂度：时间 O(n)，空间 O(1)

---

3. 三数之和

难度：中等 | LeetCode 链接

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

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

思路

排序 + 双指针。固定第一个数，剩下两个数用双指针查找，注意去重。

代码

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(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int target = -nums[i];
            int l = i+1,r=nums.length -1;
            while(l<r){
                //如果nums[l]+nums[r] = target
                if(nums[l]+nums[r] == target){
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    //继续寻找
                    l++;
                    r--;
                    //跳过重复元素
                    while(nums[l-1]==nums[l]&&l<r){
                        l++;
                    }
                    while(nums[r+1]==nums[r]&&l<r){
                        r--;
                    }
                    continue;
                }
                //如果nums[l]+nums[r] < target l++
                if(nums[l]+nums[r] < target){
                    l++;
                    continue;
                }
                //如果nums[l]+nums[r] > target r--
                if(nums[l]+nums[r] > target){
                    r--;
                }
            }
        }
        return res;
    }
}

复杂度：时间 O(n²)，空间 O(1)

---

总结

题目	核心技巧	时间	空间
移动零	双指针交换	O(n)	O(1)
盛最多水的容器	双指针 + 移动短边	O(n)	O(1)
三数之和	排序 + 双指针 + 去重	O(n²)	O(1)