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

283. 移动零

class Solution {public void moveZeroes(int[] nums) {int length = nums.length;// 定义双指针 left currentint 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;}}

解题思路

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

1. 问题分析：

   • 给定一个整数数组，需要将所有零移动到数组末尾。
   • 非零元素必须保持原有顺序。
   • 要求原地操作（不创建新数组）。

2. 双指针设计：

   • 左指针（left）：指向当前已处理序列的末尾（即下一个非零元素应放置的位置）。
   • 右指针（i）：遍历数组的指针，用于发现非零元素。

3. 算法流程：

   • 初始化 left = 0。
   • 遍历数组（i 从 0 到 n-1）：
     • 若 nums[i] != 0（发现非零元素）：
       • 交换 nums[left] 和 nums[i]。
       • left 右移一位。
   • 遍历结束后，所有零已被移动到数组末尾。

4. 关键点解释：

   • 保持非零元素顺序：每次交换将非零元素移到 left 位置，left 按顺序递增，确保非零元素按原序排列。
   • 零的移动：非零元素被交换到前面后，零自然被“挤”到后面。
   • 原地操作：仅使用常量额外空间（双指针）。

5. 示例模拟：

   • 输入：[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轴形成的容器能容纳的最大水量。容器的容量由两个因素决定：

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

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

算法步骤：

1. 初始化指针：

   • left 指向数组起始位置（左边界）
   • right 指向数组末尾位置（右边界）
   • max_area 记录最大面积，初始化为0

2. 双指针扫描：

   • 当 left < right 时循环：
     a. 计算当前面积：
     当前面积 = min(左高度, 右高度) × (右索引 - 左索引)
     b. 更新最大面积：
     比较当前面积与历史最大值
     c. 移动指针：
     • 若左高度 < 右高度 → 左指针右移 (left++)
     • 否则 → 右指针左移 (right--)

3. 返回结果：
   循环结束后返回记录的最大面积 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。核心挑战在于：

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

核心思想：

1. 排序预处理：

   • 首先对数组排序，使相同元素相邻，便于跳过重复解
   • 排序后可以利用有序性进行高效搜索

2. 固定+双指针：

   • 外层循环固定一个数 nums[i]
   • 内层使用双指针在剩余数组中寻找两数之和等于 -nums[i]

算法步骤：

1. 排序数组：
   Arrays.sort(nums);

2. 外层循环：

   • 遍历数组，固定当前数 nums[i]
   • 跳过重复固定数：
     if(i>0 && nums[i]==nums[i-1]) continue;

3. 双指针搜索：

   • 初始化指针：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)栈空间）
  • 结果存储空间不计入复杂度分析

总结

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

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