双指针

双指针

1 两数之和（Two Sum）：leetcode.cn/problems/two-sum/

给定整数数组 nums 和目标值 target，在数组中找出两个数使得它们的和等于 target，并返回这两个数的下标。

• 你可以假设每种输入只会对应一个答案；
• 同一个元素不能使用两次；
• 下标返回顺序任意。

思路与解答（双指针 + 排序）

1. 双指针适用于有序数组；对于无序 nums 先排序。
2. 为了返回原下标：先得到“按值排序的索引序列” idx_sorted，再构造对应的 nums_sorted。
3. 在 nums_sorted 上用双指针：和小则 l += 1，和大则 r -= 1，相等时返回 [idx_sorted[l], idx_sorted[r]]。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # idx_sorted: 排序后元素在原数组中的下标序列
        idx_sorted = sorted(range(len(nums)), key=nums.__getitem__)

        # nums_sorted: 排序后的数值序列（与 idx_sorted 一一对应）
        nums_sorted = [nums[i] for i in idx_sorted]

        l, r = 0, len(nums_sorted) - 1
        while l < r:
            s = nums_sorted[l] + nums_sorted[r]
            if s < target:
                l += 1
            elif s > target:
                r -= 1
            else:
                return [idx_sorted[l], idx_sorted[r]]

        return [-1, -1]

复杂度分析

• 时间复杂度：排序为$(O(n\log n))$，双指针扫描为$(O(n))$，总计$(O(n\log n))$。
• 空间复杂度：额外保存idx_sorted和nums_sorted，为$(O(n))$。

3 三数之和：leetcode.cn/problems/3sum/

给定整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k、j != k，且 nums[i] + nums[j] + nums[k] == 0。返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

思路与解答（排序 + 双指针）

1. 先排序，将三数之和转化为：枚举一个数 nums[i]，在区间 (i, n-1] 内做“两数之和 = -nums[i]`”的双指针搜索。
2. 去重：i 去重；命中答案后对 j、k 跳过连续重复值。
3. 剪枝：若当前最小三数和已大于 0，直接结束；若当前最大三数和仍小于 0，跳过该 i。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)

        for i in range(n - 2):
            # i 去重
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # 剪枝：最小三数和 > 0，后面只会更大
            if nums[i] + nums[i + 1] + nums[i + 2] > 0:
                break
            # 剪枝：最大三数和 < 0，这个 i 不可能有解
            if nums[i] + nums[n - 2] + nums[n - 1] < 0:
                continue

            target = -nums[i]
            j, k = i + 1, n - 1
            while j < k:
                s = nums[j] + nums[k]
                if s < target:
                    j += 1
                elif s > target:
                    k -= 1
                else:
                    res.append([nums[i], nums[j], nums[k]])

                    # j, k 去重
                    j += 1
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                    k -= 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1

        return res

11 盛最多水的容器：leetcode.cn/problems/container-with-most-water/

思路与解答（双指针）

1. 用左右指针 l=0, r=n-1 表示两条边，当前容量为 (r-l) * min(height[l], height[r])，并维护最大值。
2. 每次移动“较短”的那一侧：若 height[l] < height[r] 则 l += 1，否则 r -= 1。因为面积受短板限制，移动长板宽度变小且短板不变/更短，不可能得到更优解。
3. 重复直到 l >= r，过程中不断更新最大面积。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        area = (r - l) * min(height[l], height[r])
        while l < r:
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
            area = max(area, (r - l) * min(height[l], height[r]))
        return area

42 接雨水：leetcode.cn/problems/trapping-rain-water/

思路与解答（双指针）

1. 维护左右指针 l=0, r=n-1，以及两侧当前最高挡板 left_h、right_h（分别是 [0..l] 与 [r..n-1] 的最大高度）。
2. 若 left_h < right_h，说明左侧当前位置能接的水只由 left_h 决定（右侧一定有更高挡板兜住），因此累加 left_h - height[l] 并 l += 1；反之对右侧累加 right_h - height[r] 并 r -= 1。
3. 扫描过程中不断更新 left_h/right_h，直到指针交错，累加值即为总雨水量，时间 O(n)、空间 O(1)。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans, l, r = 0, 0, len(height) - 1
        left_h, right_h = 0, 0
        while l <= r:
            left_h = max(left_h, height[l])
            right_h = max(right_h, height[r])
            if left_h < right_h:
                ans += left_h - height[l]
                l += 1
            else:
                ans += right_h - height[r]
                r -= 1
        return ans