当前位置：首页 > news >正文

每日算法精讲 Day 3(双指针基础) | 移动零复写零与 LeetCode 202. 快乐数与 LeetCode 11.盛最多水的容器与 LeetCode 611 有效三角形的个数

news 2026/8/29 18:08:40

引言：

283. 移动零

题目分析

逻辑梳理（快排分区思想）

代码实现

复杂度分析

1089. 复写零

题目分析

逻辑梳理

代码实现

复杂度分析

202. 快乐数

题目分析

逻辑梳理（快慢指针判环）

代码实现

复杂度分析

11. 盛最多水的容器

题目分析

逻辑梳理（对向双指针）

代码实现

复杂度分析

611. 有效三角形的个数

题目分析

逻辑梳理（排序 + 双向指针）

代码实现

复杂度分析

结语：

引言：

双指针是算法面试中最常用、最高效的技巧之一。它通过维护两个指针的相对位置，将暴力 O(n²) 的解法优化到 O(n)，且通常只需 O(1) 的额外空间。本文精选 5 道 LeetCode 经典题目，从数组操作到数学规律，带你掌握双指针的核心思想。

接下来进入正文————>

283. 移动零

题目分析

将数组中的所有 0 移动到末尾，同时保持非零元素的相对顺序不变。

逻辑梳理（快排分区思想）

维护两个指针l和r：

l左侧：全部为非零元素
l到r之间：全部为0
r右侧：待处理区域

当r遍历完数组时，所有 0 自然被"挤"到了右侧。

代码实现

class Solution { public: void moveZeroes(vector<int>& nums) { int l = -1,r = 0; while(r<nums.size()) { if(nums[r]) swap(nums[++l],nums[r++]); else r++; } } };

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

1089. 复写零

题目分析

遍历数组，遇到 0 就复写一次，后续元素整体右移一位。要求原地修改。

逻辑梳理

如果从前往后复写，0 会占两个位置，导致后续未处理的元素被覆盖。因此采用从后往前的策略：

第一步：先找到"最后一个被复写的数"的位置
第二步：从后向前进行复写操作

代码实现

AC码

class Solution { public: void duplicateZeros(vector<int>& arr) { int cur = 0, dest = -1; while (dest < (int)arr.size()) { if (arr[cur]) dest++; else dest += 2; if (dest >= arr.size() - 1) break; cur++; } if (dest == arr.size()) { arr[dest - 1] = arr[cur]; dest -= 2; cur--; } while (cur>=0) { if (arr[cur] == 0) arr[dest--] = arr[cur]; arr[dest--] = arr[cur--]; } } };

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

202. 快乐数

题目分析

判断一个数字是否"快乐"： repeatedly 替换为各位数字的平方和，最终能否得到 1。

逻辑梳理（快慢指针判环）

将每次运算后的结果视为链表中的节点：

如果最终能得到 1，会进入1 → 1 → 1...的循环
如果不能得到 1，会进入其他循环

使用快慢指针：慢指针每次走一步，快指针每次走两步。若相遇时值为 1，则是快乐数；否则不是。

代码实现

AC码

class Solution { public: int func1(int k) { int ans = 0; while(k) { ans += pow(k%10,2); k/=10; } return ans; } bool isHappy(int n) { int slow = n; int fast = func1(n); while(slow!=fast) { slow = func1(slow); fast = func1(func1(fast)); } if(fast==1) return true; else return false; } };

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

11. 盛最多水的容器

题目分析

给定 n 条垂线，找出两条线使得与 x 轴构成的容器能盛最多的水。面积 = 两线距离 × 较短线的高度。

逻辑梳理（对向双指针）

left从最左端开始，right从最右端开始（此时宽度最大）
每次移动高度较小的指针向中间靠拢
原理：宽度在减小，只有可能通过增加高度来获得更大面积

代码实现

class Solution { public: int maxArea(vector<int>& height) { int left = 0,right = height.size()-1; int ans = min(height[left],height[right])*(right-left); while(left!=right) { if(height[left]<height[right]) left++; else right--; ans = max(ans,min(height[left],height[right])*(right-left)); } return ans; } };

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

611. 有效三角形的个数

题目分析

给定数组，统计能组成三角形的三元组个数（下标不同即可）。

逻辑梳理（排序 + 双向指针）

三角形判定：两边之和大于第三边。先排序，然后固定最长边nums[i]，用双指针找另外两边：

left = 0,right = i - 1
若nums[left] + nums[right] > nums[i]，则[left, right-1]所有元素与right组合都满足，累加right - left，然后right--
否则left++

代码实现

class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(),nums.end()); int ans = 0; for(int i = 2;i<nums.size();i++) { int left = 0,right = i-1; while(left<right) { if(nums[left]+nums[right]<=nums[i]) left++; else { ans += right-left; right--; } } } return ans; } };