双指针

LeetCode 443 https://leetcode.cn/problems/string-compression/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 为了实现原地压缩，我们可以使用双指针分别标志我们在字符串中读和写的位置。每次当读指针 read 移动到某一段连续相同子串的最右侧，我们就在写指针 write 处依次写入该子串对应的字符和子串长度即可。 在实际代码中，当读指针 read 位于字符串的末尾，或读指针 read 指向的字符不同于下一个字符时，我们就认为读指针 read 位于某一段连续相同子串的最右侧。该子串对应的字符即为读指针 read 指向的字符串。我们使用变量 left 记录该子串的最左侧的位置，这样子串长度即为 read−left+1。 特别地，为了达到 O(1) 空间复杂度，我们需要自行实现将数字转化为字符串写入到原字符串的功能。这里我们采用短除法将子串长度倒序写入原字符串中，然后再将其反转即可。 时间复杂度：O(n)，其中 n 为字符串长度，我们只需要遍历该字符串一次。 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。 ...

LeetCode 344 https://leetcode.cn/problems/reverse-string/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 由于 left+right=n−1 恒成立，所以只需要用一个变量 i 表示 left，n−1−i 就是 right。 根据上面的讨论，循环直到 i=⌊n / 2⌋ 时停止。 时间复杂度：O(n)，其中 n 为 s 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...

LeetCode 611 https://leetcode.cn/problems/valid-triangle-number/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 为了能够使用相向双指针，先对数组从小到大排序，然后枚举最长边。因为如果枚举最短边，当 a + b < c 时，增大 b 或 减少 c 都可以满足条件，无法知道移动哪一个指针。 外层循环枚举最长边 c=nums[k]，内层循环用相向双指针枚举 a=nums[i] 和 b=nums[j]，具体如下： 初始化左右指针 i=0, j=k−1。 如果 nums[i]+nums[j]>c，由于数组是有序的，nums[j] 与下标 i′ 在 [i,j−1] 中的任何 nums[i′] 相加，都是 >c 的，因此直接找到了 j−i 个合法方案，加到答案中，然后将 j 减一。 如果 nums[i]+nums[j]≤c，由于数组是有序的，nums[i] 与下标 j′ 在 [i+1,j] 中的任何 nums[j′] 相加，都是 ≤c 的，因此后面无需考虑 nums[i]，将 i 加一。 重复上述过程直到 i≥j 为止。 时间复杂度：O(n^2)，其中 n 为 nums 的长度。 空间复杂度：O(1)。忽略排序的栈开销。 ...

LCR 139 https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 双指针。 时间复杂度 O(N) ： N 为数组 actions 长度，双指针 i, j 共同遍历整个数组。 空间复杂度 O(1) ： 双指针 i, j 使用常数大小的额外空间。 ...

LeetCode 287 https://leetcode.cn/problems/find-the-duplicate-number/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题不允许修改数组，因此不能使用原地哈希。使用快慢指针法，同环形链表题目。 时间复杂度：O(n)。「Floyd 判圈算法」时间复杂度为线性的时间复杂度。 空间复杂度：O(1)。我们只需要常数空间存放若干变量。 ...

LeetCode 189 https://leetcode.cn/problems/rotate-array/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 轮转数组只需要三步，反转整个数组，反转前 k 个元素，反转后 n - k 个。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...

LeetCode 75 https://leetcode.cn/problems/sort-colors/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ O(1) 插入元素 不是插入元素，而是修改元素！ 维护 a 中 0 的个数，即改为 0 的位置，记作 p0。维护 a 中 0 和 1 的个数，即改为 1 的位置，记作 p1。 首先将 x 改为 2，如果 x <= 1，nums[p1++] = 1，如果 x == 0，nums[p0++] = 0。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...

LeetCode 26 https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/ 难度：简单 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 双指针，维护保留元素的个数。 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(1)。 ...

LeetCode 16 https://leetcode.cn/problems/3sum-closest/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 本题比三数之和增加了一个 min_diff 变量维护 |s - target| 最小值。 时间复杂度：\(O(n^2)\)，其中 n 为 nums 的长度。排序 O(nlogn)。外层循环枚举第一个数，然后 O(n) 双指针。所以总的时间复杂度为 \(O(n^2)\)。 空间复杂度：O(1)。返回值不计入，忽略排序的栈开销。 ...

LeetCode 11 https://leetcode.cn/problems/container-with-most-water/description/ 难度：中等 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 相向双指针。容器的容积是由左右两端较低的一方决定的。如果保留较低的一端，另一端相向移动。假设新的另一端比他要高，那么最低的还是他，宽度变小了，容积也变小了。假设另一端比他还低，那么宽度变小了，高度也变小了，容积还是变小。因此如果要得到更大的容积，就不能保留较低的一端，需要移动他。 时间复杂度：O(n)，其中 n 为 height 的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...