双指针题目总结

简述

双指针多用于数组中的查找，比如二分查找。

例题目录

• 1. leetcode 42. 接雨水
• 2. leetcode 658. 找到K个最接近的元素

例题

1、接雨水

题目描述：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

算法

左右两个指针分别记录左右的最高柱子，当左边最高柱子低于右边最高柱子时，左指针加一；反之当右边最高柱子低于左边最高柱子时，右指针加一。

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        """双指针"""
        n = len(height)
        left, right = 0, n - 1
        left_max, right_max = 0, 0
        ans = 0
        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])
            if left_max < right_max:
                ans += left_max - height[left]
                left += 1
            else:
                ans += right_max - height[right]
                right -= 1
        return ans 

时间复杂度：O(n)

还可以用单调栈来解答。参考

2、找到 K 个最接近的元素

题目描述：

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。

示例 1:

输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]

示例 2:

输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

说明:

k 的值为正数，且总是小于给定排序数组的长度。
数组不为空，且长度不超过 104
数组里的每个元素与 x 的绝对值不超过 104

解法

左右两个指针，分别计算与x的绝对值大小，大的就向中间靠近，左右绝对值相等时则右指针向中间靠（因为题目说与x差值相等时选择优先选择数值较小那个）。当左右指针之间的元素个数等于k时就找到了答案。

代码

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        n = len(arr)
        if n == k:
            return arr
        l, r = 0, n - 1
        while l < r:
            left = abs(arr[l] - x)
            right = abs(arr[r] - x)
            if left > right:
                l += 1
            elif left < right:
                r -= 1
            else:
                r -= 1
            if r - l + 1 == k:
                return [x for x in arr[l:r+1]]

时间复杂度O(n)
这道题还有更好的二分解法。