0 Two Pointers Basic

双指针是什么？

用两个指针（下标）在数组/链表上协同移动，通过缩小搜索范围来降低复杂度

两大类型：

类型	特征	典型题
对撞指针	一头一尾，向中间逼近	盛水容器、三数之和
快慢指针	同向移动，速度不同	移动零、链表环检测

使用双指针的条件：
- 通常数组有序（或者问题本身有单调性）
- 如果无序，往往需要先排序
双指针能降低复杂度原因：利用了单调性，使得指针不需要回退，将 O(n²) 降到 O(n)

1 快慢指针（数组原地操作）

1.1 移动零 | Easy

题目： 将数组中所有 0 移到末尾，保持非零元素的相对顺序。原地操作

[0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]

思路分析：用快慢指针，left指向当前最左边的0的位置，i找非0，然后swap

left：慢指针，始终指向下一个非零元素该放的位置
i：快指针，遍历数组寻找非零元素
left左边都是已经处理好的非零元素，每找到一个非零元素，就交换到left位置，然后left右移

走一遍[0, 1, 0, 3, 12]:

i=0, nums[0]=0  → 是0，跳过        zero=0, [0, 1, 0, 3, 12]
i=1, nums[1]=1  → 非0，和zero交换  zero=1, [1, 0, 0, 3, 12]
i=2, nums[2]=0  → 是0，跳过        zero=1, [1, 0, 0, 3, 12]
i=3, nums[3]=3  → 非0，和zero交换  zero=2, [1, 3, 0, 0, 12]
i=4, nums[4]=12 → 非0，和zero交换  zero=3, [1, 3, 12, 0, 0]

踩坑记录：搞清楚两个指针的含义以及交换条件

代码：

 1class Solution:
 2    def moveZeroes(self, nums: List[int]) -> None:
 3        """
 4        Do not return anything, modify nums in-place instead.
 5        """
 6        zero = 0
 7        for i in range(len(nums)):
 8            if nums[i] != 0:
 9                nums[i], nums[zero] = nums[zero],  nums[i] # python swap
10                zero += 1

复杂度：

时间 O(n)，一次遍历
空间 O(1)，原地操作

关联题目：

移除元素（LC 27）： 同样的快慢指针模板，只是把 != 0 换成 != val
删除有序数组中的重复项（LC 26）： if nums[fast] != nums[slow - 1]: ...

题目： 一个 非严格递增排列 的数组 nums ，原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。 nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。

思路分析：使用快慢指针

踩坑记录：搞清楚两个指针的含义以及交换条件

代码：

1class Solution:
2    def removeDuplicates(self, nums: List[int]) -> int:
3        left = 1
4        for i in range(len(nums)):
5            if i > 0 and nums[i] != nums[i-1]:
6                nums[left] = nums[i]
7                left += 1
8        return left

复杂度：

时间 O(n)，一次遍历
空间 O(1)，原地操作

Tempalte：

1slow = 0
2for fast in range(len(nums)):
3    if 满足保留条件:
4        nums[slow] = nums[fast]  # 或者 swap
5        slow += 1
6return slow

2 X数之和

2.1 两数之和无序版｜Easy

题目：给定整数数组 nums 和目标值 target，找出和为 target 的两个元素的下标。假设恰好有一个解，同一元素不能用两次

思路分析：

暴力：两层for loop，时间复杂度是$O(n^2)$
哈希：
- 对于当前num，我需要找target -num $\Rightarrow$ 之前遍历过的nums里面是否存在 $\Rightarrow$哈希查找
- 一边遍历，一边把已经见过的数存进哈希表，对于每一个新遍历的数，先找哈希表中是否存在target - num
- num作为key，index作为value

踩坑记录：一定要清楚这个哈希表数据结构怎么构造的，num as key, value as index

代码：

1class Solution:
2    def twoSum(self, nums: List[int], target: int) -> List[int]:
3        seen = {}
4        for idx, num in enumerate(nums):
5            complement = target - num
6            if complement in seen:
7                return [seen[complement], idx]
8            seen[num] = idx

复杂度：

时间：O(n)
空间：O(n)

关联题目：

如果数组有序？ $\Rightarrow$ 双指针
如果需要返回所有配对？$\Rightarrow$ 注意需要去重，用Counter更方便
三数之和？$\Rightarrow$ 排序 + 双指针

2.2两数之和有序版｜ Medium

题目：给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2
每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素
你所设计的解决方案必须只使用常量级的额外空间

思路分析：

数组已经有序 $\Rightarrow$ 双指针，不需要哈希表

左指针l从最小值开始，右指针r从最大值开始，根据条件分别移动左右指针

踩坑记录：注意返回下标从1开始

代码：

 1class Solution:
 2    def twoSum(self, numbers: List[int], target: int) -> List[int]:
 3        l, r = 0, len(numbers) - 1
 4
 5        while l < r:
 6            s = numbers[l] + numbers[r]
 7            if s < target:
 8                l += 1
 9            elif s > target:
10                r -= 1
11            else:
12                return [l+1, r+1]

复杂度:

时间：O(n) 双指针最多哥走n步
空间：O(1) 只用了两个指针，和无序版O(n)对比，有序版空间复杂度更优

2.3 三数之和 | Medium

题目： 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

思路分析：“两数之和"的升级版

关键步骤：排序 + 固定一个数 + 双指针找另外两个数
排序后的好处：
1. 可以用双指针
2. 方便跳过重复元素

踩坑记录: 想清楚如何剪枝&判断重复条件

剪枝：if nums[i] > 0: break
外层i去重：if i > 0 and nums[i] == nums[i-1]: continue
内层l, r去重：找到一组解后跳过相同值

代码：

 1class Solution:
 2    def threeSum(self, nums: list[int]) -> list[list[int]]:
 3        nums.sort()
 4        n = len(nums)
 5        result = []
 6
 7        for i in range(n - 2):
 8            if nums[i] > 0:
 9                break
10            if i > 0 and nums[i] == nums[i - 1]:
11                continue
12
13            l, r = i + 1, n - 1
14            target = -nums[i]
15            while l < r:
16                s = nums[l] + nums[r]
17                if s > target:
18                    r -= 1
19                elif s < target:
20                    l += 1
21                else:
22                    result.append([nums[i], nums[l], nums[r]])
23                    while l < r and nums[l] == nums[l + 1]:
24                        l += 1
25                    while l < r and nums[r] == nums[r - 1]:
26                        r -= 1
27                    l += 1
28                    r -= 1
29
30        return result

复杂度：

时间：O($n^2$)
空间：O(1)

拓展：

Q：为什么要先排序？ A：排序后才能用双指针 + 去重

Q：时间复杂度是否可以优于O($n^2$)？ A：不能，这是问题下界

2.4 四数之和｜ Medium

题目：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

思路分析：

在三数之和的基础上再套一层循环。排序后固定两个数 nums[i] 和 nums[j]，然后在剩余部分用双指针找两数之和等于 target - nums[i] - nums[j]。
三层去重：i 层跳重复、j 层跳重复、找到解后 l 和 r 跳重复

踩坑记录：三重去重：

i重复：i > 0 and nums[i] == nums[i - 1]
j重复：j > i + 1 and nums[j] == nums[j - 1]
l, r重复：

代码：

 1class Solution:
 2    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
 3        nums.sort()
 4        n = len(nums)
 5        result = []
 6
 7        for i in range(n - 3):
 8            if i > 0 and nums[i] == nums[i - 1]:
 9                continue
10
11            for j in range(i + 1, n - 2):
12                if j > i + 1 and nums[j] == nums[j - 1]:
13                    continue
14
15                l, r = j + 1, n - 1
16                targetsum = target - nums[i] - nums[j]
17                while l < r:
18                    s = nums[l] + nums[r]
19                    if s < targetsum:
20                        l += 1
21                    elif s > targetsum:
22                        r -= 1
23                    else:
24                        result.append([nums[i], nums[j], nums[l], nums[r]])
25                        while l < r and nums[l] == nums[l + 1]:
26                            l += 1
27                        while l < r and nums[r] == nums[r - 1]:
28                            r -= 1
29                        l += 1
30                        r -= 1
31        
32        return result

复杂度：

时间 O(n³)：两层循环 O(n²) × 双指针 O(n)
空间 O(1)（不计结果和排序）

3 盛最多水的容器 | Medium

题目： 给定 n 个非负整数 height[0..n-1]，每个代表坐标 (i, height[i]) 处的一条竖线。选两条线与 x 轴构成容器，求最多能盛多少水。 ![[lc11.png]]

思路分析：

暴力：两层for loop $\Rightarrow$ O($n^2$)
双指针：面积area = min(height[l], height[r]) * (r - l)
- 初始l = 0, r = n - 1，宽度最大
- 每次应该移动较矮的线，移动高的线一定会让面积减小

踩坑记录：

证明正确性：假设当前 height[l] < height[r]：对于所有以 l 为左边界的配对 (l, r'), r' < r：宽度更小，高度仍受限于 height[l]，所以面积一定更小。因此可以安全地淘汰所有 (l, r') 的配对，即 l += 1

代码:

 1class Solution:
 2    def maxArea(self, height: List[int]) -> int:
 3        l, r = 0, len(height) - 1
 4        best = 0
 5
 6        while l < r:
 7            area = min(height[l], height[r]) * (r - l)
 8            best = max(best, area)
 9            if height[l] < height[r]: # 两边相等时，移动哪边都可以
10                l += 1
11            else:
12                r -= 1
13        
14        return best

复杂度：

时间：O(n)
空间：O(1)

双指针刷题总结

0 Two Pointers Basic

1 快慢指针（数组原地操作）

1.1 移动零 | Easy

1.2 移除元素| Easy

1.3 删除有序数组中的重复项 | Easy

2 X数之和

2.1 两数之和无序版｜Easy

2.2两数之和有序版｜ Medium

2.3 三数之和 | Medium

2.4 四数之和｜ Medium

3 盛最多水的容器 | Medium

0 Two Pointers Basic#

1 快慢指针（数组原地操作）#

2 X数之和#

0 Two Pointers Basic

1 快慢指针（数组原地操作）

2 X数之和