283. 移动零 - 力扣（LeetCode）
题目分析：
题目要求将数组 nums 中所有 0 移动至数组末尾，同时保持其他非零元素的相对顺序不变，并且要求在原数组上进行操作。
核心要求：
- 0 要移动至数组末尾
- 非零元素相对位置不变
- 在原数组上进行操作
解法一（暴力使用数组方法）
遍历数组将其中所有为 0 的数直接使用splice删除并且记录 0 的个数，最后通过push填入“移动”的 0
1var moveZeroes = function(nums) { 2 let n = 0; 3 for(let i = 0; i < nums.length;){ 4 if(nums[i] == 0){ 5 n++; 6 nums.splice(i, 1); 7 } else i++; 8 } 9 for(let j = 0; j < n; j++){ 10 nums.push(0); 11 } 12 return nums; 13}; 14
⏱️ 时间复杂度分析
splice(i, 1)的代价：
在数组中间删除一个元素，需要将 i 后面的所有元素向前移动一位。
--> 时间复杂度为 O(k) ，其中 k 是从 i 到末尾的元素个数。- 最坏的情况：假设数组中有
z个 0，且它们分布在前面：- 第 1 个 0 被删时，移动 n-1 个元素
- 第 2 个 0 被删时，移动 n-2 个元素
- ...
- 最坏情况总移动次数 ≈ (n-1) + (n-2) + ... + (n-z) ≈ O(n²)
（例如输入[0,0,0,...,0,1]）
push(0)的代价： 是 O(z)，可忽略。
最坏时间复杂度：O(n²)
注：
JavaScript 数组在底层通常是连续内存，而
splice(i, 1)会触发 大量元素的内存拷贝⚠️ 尽量避免在循环中使用
splice删除元素，尤其是在处理大数组时，性能会急剧下降
解法二（双指针 + 交换）
题目的问题本质上是将所有非零的元素按照原先的相对顺序排在数组的最前方，那么不妨通过一个指针安排非零元素的位置，而另一个指针来查找所有非零的元素并且通过交换来将其放置在正确的位置。
1var moveZeroes = function(nums) { 2 let j = 0; 3 for(let i = 0; i < nums.length; i++) { 4 if (nums[i] != 0) { 5 let temp = nums[j]; 6 nums[j] = nums[i]; 7 nums[i] = temp; 8 // [灵茶山艾府] 灵神做法： 9 // [nums[j],nums[i]] = [nums[i],nums[j]]; （更简洁、更现代） 10 j++; 11 } 12 } 13}; 14
⏱️ 时间复杂度分析
- 单次遍历：
使用for循环从i = 0到i = nums.length - 1遍历数组一次 → O(n) - 交换操作：
每次遇到非零元素时，执行一次交换（通过临时变量或解构赋值），该操作为 O(1) ；
由于i单调递增、j不回退，每个元素最多被访问和交换一次 → 总交换开销为 O(n) - 总时间复杂度：O(n) + O(n) = O(n)
11. 盛最多水的容器 - 力扣（LeetCode）
题目分析：
题目要求从给定的整数数组 height 中选择两条垂线，使得它们与 x 轴共同构成的容器可以容纳最多的水，并返回该最大水量。
核心要求：
- 容器不能倾斜
- 较短的一条决定容器的高度
- 容器的宽度为索引之差
- 目标是使容器的面积（水量）最大化
本题本质上是在所有可能的垂线对 (i, j)（其中 i < j）中，寻找使面积
area=(j−i)×min(height[i],height[j])\text{area} = (j - i) \times \min(\text{height}[i], \text{height}[j])area=(j−i)×min(height[i],height[j])
最大的组合。
解法（双指针）
题目本意就是要找到两个尽可能远且尽可能高的数据，那么不妨先把两个指针放置最远，再通过逐一减小距离来找到尽可能高的数据来平衡距离的缩减。
优化： 由于距离在缩减，所以如果数据还减小的话，那么总量一定减小，所以只能牺牲更小的一边向中心查找是否能找到更高的数据。
1var maxArea = function(height) { 2 let left = 0, right = height.length - 1; 3 // 总面积 4 let m = 0; 5 6 while(left < right) { 7 // 计算当前面积并比较大小 8 area = (right - left) * Math.min(height[left], height[right]) 9 m = Math.max(area, m); 10 // 判断哪方更小，哪方移动 11 if (height[left] < height[right]) left++; 12 else right--; 13 } 14 return m; 15} 16
15. 三数之和 - 力扣（LeetCode）
题目分析：
题目要求从给定的整数数组 nums 中找出所有下标不重复的三元组，使得三个数的和为 0，并且每组不同。
核心要求：
- 三元组中的三个数之和必须等于 0
- 结果中不能包含重复的三元组
- 三元组内的元素可以按任意顺序排列
- 每个三元组中的元素必须来自数组中不同的位置（但值可以相同）
本题本质上是在数组中寻找所有满足
nums[i]+nums[j]+nums[k]=0\text{nums}[i] + \text{nums}[j] + \text{nums}[k] = 0 \quadnums[i]+nums[j]+nums[k]=0
的三元组，并确保结果集合中无重复。
解法（排序 + 双指针）
暴力枚举需要三重循环，这样时间复杂度将会飙升到 O(n³)，效率极其低下，所以我们采用排序 + 固定一个数 + 双指针的优化策略。
关键思想：
- 先对数组排序，后续可以通过大小关系移动指针。当到达分界点
0时，后续所有值无论如何增加总值都不会为零（优化点）； - 固定第一个数
nums[i]，将其转化为“在剩余数组中找两数之和为-nums[i]”的问题； - 使用双指针
left = i+1、right = n-1向中间收缩，根据当前和与目标值的大小关系移动指针； - 跳过重复值：
- 若
nums[i] == nums[i-1]，跳过重复； - 找到一组解后，继续跳过
left和right的重复值，防止重复答案。
- 若
1var threeSum = function(nums) { 2 // 先排序：升序排列，使用JS内置的 sort 方法 3 // sort() 根据返回值决定 a 和 b 谁排在前面 4 // a - b <= 0 ==> 顺序为 a, b 5 // a - b > 0 ==> 顺序为 b, a 6 nums.sort((a, b) => a - b); 7 const res = []; 8 9 // 固定第一个数 nums[i] 10 for (let i = 0; i < nums.length - 2; i++) { 11 // 最小值已大于 0，后续不可能有解 12 if (nums[i] > 0) break; 13 14 // 跳过重复的起始值，避免重复三元组 15 if (i > 0 && nums[i] === nums[i - 1]) continue; 16 // 双指针 17 let left = i + 1; 18 let right = nums.length - 1; 19 20 while (left < right) { 21 const sum = nums[i] + nums[left] + nums[right]; 22 if (sum === 0) { 23 res.push([nums[i], nums[left], nums[right]]); 24 25 // 移动双指针，继续查找 26 left++; 27 right--; 28 // 跳过重复组 29 while (left < right && nums[left] === nums[left - 1]) left++; 30 while (left < right && nums[right] === nums[right + 1]) right--; 31 } else if (sum < 0) { 32 // 和太小，需增大 → 左指针右移 33 left++; 34 } else { 35 // 和太大，需减小 → 右指针左移 36 right--; 37 } 38 } 39 } 40 return res; 41}; 42
⏱️ 时间复杂度分析
- 排序操作：
调用nums.sort((a, b) => a - b)对数组进行升序排序，JavaScript 引擎通常采用高效排序算法，时间复杂度 --> O(n log n) 。 - 外层循环：
for循环遍历i从0到nums.length - 3，时间复杂度 --> O(n) 。 - 内层双指针扫描：
对于每个固定的i，left和right从两端向中间移动，每个元素在该轮中最多被访问一次，因此每轮内层循环的时间复杂度 --> O(n) 。
由于外层循环执行 O(n) 次，本应当为 O(n²)，但是并非每轮都走完整个数组，所以最坏情况下 --> O(n²)。 - 总时间复杂度：排序 O(n log n) + 双指针主逻辑 O(n²) = O(n²)
42. 接雨水 - 力扣（LeetCode）
题目分析：
题目要求计算在给定的非负整数数组 height 所表示的柱状图中，能接住多少单位的雨水。每个元素 height[i] 表示位置 i 处柱子的高度，宽度均为 1。
核心要求：
- 雨水只能积在“凹陷”区域，即两侧有更高柱子的位置；
- 每个位置能接的雨水量 = min(左侧最高柱, 右侧最高柱) - 当前高度（若结果为正，否则为 0）；
- 不能倾斜容器，雨水垂直下落并被两侧柱子围住；
- 目标是返回整个结构能储存的总雨水量。
本题本质上是：对每个位置 i，快速确定其左侧最大高度和右侧最大高度，从而计算该位置的积水。
解法（双指针 + 动态边界）
暴力解法需对每个位置遍历左右求最大值，时间复杂度 O(n²)。即使使用额外数组预处理左右最大值可优化至 O(n)，但是空间占用还是过大。
所以解法采用双指针从两端向中间收缩，再利用贪心思想实现 O(1) 空间、O(n) 时间 的最优解。
关键思想：
- 维护两个变量
lmax和rmax，分别表示当前left指针左侧（含自身）的最大高度，以及right指针右侧（含自身）的最大高度； - 比较
lmax与rmax：- 若
lmax < rmax，说明left位置的积水由左侧最大值决定（因为右侧存在更高的边界），此时可安全计算left处的积水； - 否则，
right位置的积水由右侧最大值决定，计算right处的积水；
- 若
- 每次只移动较矮一侧的指针，确保另一侧始终存在足够高的“挡板”，从而保证当前积水计算的正确性。
- 并且两个指针相遇的位置一定为最高的柱子，这个柱子是无法装水的。
1var trap = function(height) { 2 // 创建双指针 3 let left = 0; 4 let right = height.length - 1; 5 6 let m = 0; // 总雨水量 7 let lmax = 0, rmax = 0; // 当前左右侧最大高度 8 9 while (left < right) { 10 // 更新左右侧最大高度 11 lmax = Math.max(lmax, height[left]); 12 rmax = Math.max(rmax, height[right]); 13 14 if (lmax < rmax) { 15 // 左侧最大值更小 → left 位置的积水由 lmax 决定 16 m += lmax - height[left]; 17 left++; 18 } else { 19 // 右侧最大值更小或相等 → right 位置的积水由 rmax 决定 20 m += rmax - height[right]; 21 right--; 22 } 23 } 24 return m; 25}; 26
⏱️ 时间复杂度分析
- 双指针遍历：
left和right从两端向中间移动，每个元素最多被访问一次，循环执行 O(n) 次。 - 每轮操作：
包括Math.max、比较、加法和指针移动，均为 O(1) 常数时间操作。 - 总时间复杂度：O(n)
- 空间复杂度：仅使用常数个变量（
left,right,m,lmax,rmax）→ O(1)
《LeetCode 热题100 --- 双指针专区》 是转载文章，点击查看原文。
