简述
双指针多用于数组中的查找，比如二分查找。
例题目录
例题
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)
这道题还有更好的二分解法。
