【LeetCode 热题 100】（二）双指针-EW帮帮网

283. 移动零

class Solution {
    public void moveZeroes(int[] nums) {
        int length = nums.length;
        // 定义双指针 left current
        int left = 0;
        for (int i = 0; i < length; i++) {
            if(nums[i] != 0){
                swap(nums,left,i);
                left = left + 1;
            }
        }
    }

    private static void swap(int[] nums, int left, int i) {
        int temp = nums[left];
        nums[left] = nums[i];
        nums[i] = temp;
    }

}

解题思路

这段代码使用双指针技巧来解决移动零的问题，核心思想是在一次遍历中完成零的移动，同时保持非零元素的相对顺序。以下是详细的解题思路：

问题分析：
- 给定一个整数数组，需要将所有零移动到数组末尾。
- 非零元素必须保持原有顺序。
- 要求原地操作（不创建新数组）。
双指针设计：
- 左指针（left）：指向当前已处理序列的末尾（即下一个非零元素应放置的位置）。
- 右指针（i）：遍历数组的指针，用于发现非零元素。
算法流程：
- 初始化 left = 0。
- 遍历数组（i 从 0 到 n-1）：
  - 若 nums[i] != 0（发现非零元素）：
    - 交换 nums[left] 和 nums[i]。
    - left 右移一位。
- 遍历结束后，所有零已被移动到数组末尾。
关键点解释：
- 保持非零元素顺序：每次交换将非零元素移到 left 位置，left 按顺序递增，确保非零元素按原序排列。
- 零的移动：非零元素被交换到前面后，零自然被“挤”到后面。
- 原地操作：仅使用常量额外空间（双指针）。
示例模拟：
- 输入：[0, 1, 0, 3, 12]
- 步骤：
  - i=0：nums[0]=0 → 跳过。
  - i=1：nums[1]=1 → 交换 nums[0] 和 nums[1] → [1, 0, 0, 3, 12], left=1。
  - i=2：nums[2]=0 → 跳过。
  - i=3：nums[3]=3 → 交换 nums[1] 和 nums[3] → [1, 3, 0, 0, 12], left=2。
  - i=4：nums[4]=12 → 交换 nums[2] 和 nums[4] → [1, 3, 12, 0, 0]。

复杂度分析

时间复杂度： $O (n)$ ，仅遍历数组一次。
空间复杂度： $O (1)$ ，仅使用常量空间存储指针。

总结

该解法高效地利用双指针在单次遍历中完成零的移动，同时保持了非零元素的顺序，满足原地操作的要求。核心在于通过交换操作逐步将非零元素前移，零元素自然后移。

11. 盛水做多的容器

class Solution {
    public int maxArea(int[] height) {
        // 1.定义双指针
        int left = 0;
        int right = height.length - 1;
        int max_area = 0;
        // 2.寻找最大的面积
        while (left < right){
            int area = Math.min(height[left],height[right]) * (right - left);
            max_area = Math.max(area, max_area);
            if(height[left] < height[right]){
                left = left + 1;
            }else{
                right = right - 1;
            }
        }
        return max_area;     
    }
}

解题思路：双指针法解决最大容器问题

问题分析：
给定一个表示垂直线高度的数组，需要找到两条垂直线与x轴形成的容器能容纳的最大水量。容器的容量由两个因素决定：

两条垂直线的距离（底边长度）
两条垂直线中较短的高度（容器高度）

核心思想：
使用双指针从数组两端向中间扫描，在每次移动中保留较高的垂直线，移动较短的垂直线，从而高效地找到最大容器面积。

算法步骤：

初始化指针：
- left 指向数组起始位置（左边界）
- right 指向数组末尾位置（右边界）
- max_area 记录最大面积，初始化为0
双指针扫描：
- 当 left < right 时循环：
  a. 计算当前面积：
  当前面积 = min(左高度, 右高度) × (右索引 - 左索引)
  b. 更新最大面积：
  比较当前面积与历史最大值
  c. 移动指针：
  - 若左高度 < 右高度 → 左指针右移 (left++)
  - 否则 → 右指针左移 (right--)
返回结果：
循环结束后返回记录的最大面积 max_area

移动策略的正确性：

关键理解：容器的容量受限于较短边
移动较高指针：底边长度减小，高度不会增加（仍受限于原较短边），面积必然减小
移动较低指针：虽然底边长度减小，但可能遇到更高的垂直线，从而获得更大面积
该策略确保不会错过可能的更大面积

示例模拟（输入：[1,8,6,2,5,4,8,3,7]）：

Step1: [1,8,6,2,5,4,8,3,7]  // 面积=min(1,7)*8=8
        ↑                 ↑   // 1<7 → 左移

Step2: [1,8,6,2,5,4,8,3,7]  // 面积=min(8,7)*7=49 (更新最大值)
           ↑             ↑   // 7<8 → 右移

Step3: [1,8,6,2,5,4,8,3,7]  // 面积=min(8,3)*6=18
           ↑          ↑      // 3<8 → 右移

...继续移动直至指针相遇，最终返回最大面积49

复杂度分析

时间复杂度：O(n)
双指针完整扫描数组一次，每个元素被访问一次
空间复杂度：O(1)
仅使用常量额外空间（指针和临时变量）

总结

该解法通过双指针从两端向中心扫描，每次移动较短边的指针，高效地找到最大容器面积。算法充分利用了容器容量受限于较短边的特性，确保在O(n)时间内解决问题，是最优解法。

15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        List<List<Integer>> list = new LinkedList<>();
        // 1.排序数组
        Arrays.sort(nums);
        // 2.固定一个数
        for (int i = 0; i < length; i++) {
            if(i>0 && (nums[i] == nums[i-1])){
                continue;
            }
            int target = nums[i];
            // 3.双指针
            int left = i+1;
            int right = length - 1;
            while (left < right){
                if(nums[left] + nums[right] == -target){
                    List<Integer> list1 = new LinkedList<>();
                    list1.add(nums[left]);
                    list1.add(nums[right]);
                    list1.add(nums[i]);
                    left = left + 1;
                    right = right - 1;
                    list.add(list1);
                    while (left < right && nums[left] == nums[left-1]){
                        left = left + 1;
                    }
                    while (left < right && nums[right] == nums[right+1]){
                        right = right - 1;
                    }
                }else if(nums[left] + nums[right] > -target){
                    right = right - 1;
                }else {
                    left = left + 1;
                }
            }
        }
        return list;
    }
}

解题思路：排序 + 双指针法解决三数之和问题

问题分析：
给定一个整数数组，找出所有不重复的三元组 [a, b, c]，使得 a + b + c = 0。核心挑战在于：

找到所有满足条件的三元组
避免返回重复解
高效实现（不能使用暴力三重循环）

核心思想：

排序预处理：
- 首先对数组排序，使相同元素相邻，便于跳过重复解
- 排序后可以利用有序性进行高效搜索
固定+双指针：
- 外层循环固定一个数 nums[i]
- 内层使用双指针在剩余数组中寻找两数之和等于 -nums[i]

算法步骤：

排序数组：
Arrays.sort(nums);
外层循环：
- 遍历数组，固定当前数 nums[i]
- 跳过重复固定数：
  if(i>0 && nums[i]==nums[i-1]) continue;
双指针搜索：
- 初始化指针：left = i+1, right = length-1
- 目标值：target = -nums[i]
- 当 left < right 时循环：
  a. 找到有效三元组：
  nums[left] + nums[right] == target
  - 记录三元组 [nums[i], nums[left], nums[right]]
  - 左右指针同时向中间移动
  - 跳过重复值：
```
while(left < right && nums[left]==nums[left-1]) left++;
while(left < right && nums[right]==nums[right+1]) right--;
```
  b. 和过大：
  nums[left] + nums[right] > target
  - 右指针左移：right--
    c. 和过小：
    nums[left] + nums[right] < target
  - 左指针右移：left++

关键点解释：

避免重复解：
- 固定数层跳过重复值
- 找到解后跳过相同左右指针值
双指针高效性：
利用排序后的有序性，通过指针移动快速定位解
时间复杂度优化：
从暴力解法的 O(n³) 优化到 O(n²)

示例模拟（输入：[-1,0,1,2,-1,-4]）：

排序后：[-4,-1,-1,0,1,2]

Step1: 固定 -4 → target=4
  双指针：[-1,-1,0,1,2]
  -1+2=1<4 → left++ → -1+2=1<4 → left++ → 0+2=2<4 → left++ → 1+2=3<4 → 结束

Step2: 固定第一个 -1 → target=1
  双指针：[-1,0,1,2]
  -1+2=1=target → 记录[-1,-1,2]
  移动指针：left++(0), right--(1)
  0+1=1=target → 记录[-1,0,1]
  结束

Step3: 跳过重复的第二个 -1 → 结束

复杂度分析

时间复杂度：O(n²)
- 排序：O(n log n)
- 双指针循环：外层O(n)，内层O(n)，总计O(n²)
空间复杂度：O(1) 或 O(n)
- 取决于排序算法（库函数一般为O(log n)栈空间）
- 结果存储空间不计入复杂度分析

总结

该解法通过排序预处理+双指针技巧，高效解决了三数之和问题：

排序使相同元素相邻，便于跳过重复解
固定一个数转化为两数之和问题
双指针在有序数组中高效搜索
精心设计的跳过逻辑避免重复解
时间复杂度从O(n³)优化到O(n²)，是最优解法之一

【LeetCode 热题 100】（二）双指针

283. 移动零

解题思路

复杂度分析

总结

11. 盛水做多的容器

解题思路：双指针法解决最大容器问题

复杂度分析

总结

15. 三数之和

解题思路：排序 + 双指针法解决三数之和问题

复杂度分析

总结

网站公告

今日签到

热门文章

最新发布