前言

双指针是一种用于解决区间问题的算法，这类算法通常的复杂度都是$\Theta(n)$。其实，我们可以将二分看作一种特殊的双指针，每次筛选掉一半的数据。同样的，双指针也可以看作一种特殊的二分，只不过每次通常筛选掉一个数据。

简单的例子：回文串的判断

这道题可以通过LeetCode 125访问，这道题的一个AC解是：

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            while not (s[left].isalpha() or s[left].isnumeric()) and left < right:
                left += 1
            while not (s[right].isalpha() or s[right].isnumeric()) and left < right:
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True

这道题的思想很简单，每次判断左右两个字符，如果一致，就左指针右移一位，右指针左移一位，判断下一个字符。这道题体现了双指针的基本写法，在区间上，首先将指针置于左右两侧，然后进行必要的操作，随后移动两个指针（或某一个指针），满足$O(n)$的复杂度。双指针算法的重要之处在于指针的移动方法。

简单的例子：二和问题

这道题可以通过LeetCode 167访问，这道题的一个AC解是：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            curr_sum = numbers[left] + numbers[right]
            if curr_sum < target:
                left += 1
            elif curr_sum > target:
                right -= 1
            else:
                return [left+1, right+1]

由于这道题已经排好序了，所以我们完全可以应用双指针算法来解决这个问题，左右指针对着的值相加，然后判断这个值的大小，如果这个值过大了，证明我们需要缩小，就将右指针左移；如果值太小，就要左指针右移。

这里是双指针的一个另一个特点——它对具有一定单调性的区间效果很好。对于回文串，这个单调性是通过回文串的性质来体现的，即每个字母只和中央对称过去的字母有关。在这道题中，由于序列排好序了，那么通过指针移动的方向，就能够判断出指针所指向值的和的变化方式。

中等的例子：接雨水青春版

这道题可以通过LeetCode 11访问，这道题的一个AC解是：

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

这道题的单调性就没有那么显然——是通过接雨水的原理体现的。接雨水需要两个边，这两个边之中的最小值为实际的接雨水的高，宽则是两个边的“横坐标”之差。此外，由于左右指针是从外向内收缩的，那么接雨水的宽是单调递减的。那么，当我们双指针指向两条边的时候，其中对于短边来说，当前情况是这条短边参与组合的所有的容器中，接的雨水最多的。这个时候需要长边指针向内收。

这个说法一定正确吗？我们来证明一下，最开始假设：两条指针指向的边长度为$d_1, d_2$，坐标为$x_1, x_2$，那么假设二者中间有一条更长或者更短的边，其长度为$d$，坐标为$x$，那么它所参与的左右两个容器的容积分别为$(x-x_1)\min(d,d_1)$和$(x_2-x)\min(d,d_2)$，我们知道：
$$
(x-x_1)<x_2-x_1,(x_2-x)<x_2-x_1
$$
并且左、右边容器的高最高分别也就是$d_1$和$d_2$，所以左右两个容器的容积必然小于总容积，那么“对于短边来说，当前情况是这条短边参与组合的所有的容器中，接的雨水最多的”这句话是成立的。

随着指针变化，又会怎么变化呢？其实，结论也是成立的，因为挪动的指针指向的边，是较短边，这条边的最大雨水容量已经找出来了，就没必要继续考虑了。

这便是这道题单调性的来源。

中等的例子：三和问题

这道题可以通过LeetCode 15访问，一个AC解是：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        l, r, m = 0, len(nums) - 1, 1
        result = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i+1, len(nums) - 1
            while l < r:
                curr_val = nums[l] + nums[r]
                if curr_val == -nums[i]:
                    result.append([nums[i], nums[l], nums[r]])
                    l += 1
                    while nums[l] == nums[l - 1] and l < r:
                        l += 1
                elif curr_val > -nums[i]:
                    r -= 1
                else:
                    l += 1
        return result

这道题的解法是，首先创造单调性——排序。然后通过定一议二的方法利用双指针求解。这道题的难度在于不是那么好想出来“排序-迭代-双指针”的解法。

困难的例子：接雨水

这道题可以通过LeetCode 42访问，一个AC解是：

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

这个解是我复制粘贴得来的，并非我自己手搓的。这道题我更习惯于单调栈的解法。

这道题的关键在于，明白接雨水的原理——一个容器是由短边控制的。我们首先从左右两边向中间迭代，如果右边有比左边高的边，那么左边这条边一定能形成一个以这条边为短边的容器，在左侧边和右侧边中间的点，其高度往上，一定能形成一个小水洼，水的高度为left_max-height[l]。

这道题的单调性在哪里？其实，这道题的单调性就在于，一个容器的高度变化是——先递减再递增的。