双指针

11. Container With Most Water

考虑使用对撞双指针，不断更新面积（可容纳水量）：

任意时刻，无论移动还是，均会使宽度缩小1格，即，但考虑高度：

• 若移动短板，可能增加；
• 若移动长板，必定减小或不变。

故在每个时刻都移动短板，直到两指针相遇，记录最大面积。

class Solution:
    def maxArea(self, heights: List[int]) -> int:
        l, r = 0, len(heights) - 1
        res = (r - l) * min(heights[l], heights[r])  # 初始化
        while l < r:                                 # l == r，宽度为0，不必计算
            if heights[l] < heights[r]:
                l += 1
            else:
                r -= 1
            res = max(res, (r - l) * min(heights[l], heights[r]))
        return res

• 时间复杂度：
• 空间复杂度：

15. 3Sum

注意需要返回的是而非，故可以先对数组进行排序，然后利用双指针缩减搜索空间的办法，降低时间复杂度。
实际上，固定，对撞双指针的搜索，就是转化成了两数之和（有序）。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if not nums or len(nums) < 3:
            return []
        n = len(nums)
        nums.sort()
        res = []
        for k in range(n - 2):
            if nums[k] > 0:                   # 剪枝：数组已经有序，三数之和不可能为'0'
                break
            if k and nums[k] == nums[k-1]:    # 去重：'k > 0'不可缺少
                continue                      # Python中nums[-1]仍有意义
            i, j = k + 1, n - 1               # 双指针：缩减搜索空间
            while i < j:
                sum_3 = nums[k] + nums[i] + nums[j]
                if sum_3 < 0:
                    i += 1
                elif sum_3 > 0:
                    j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    while i < j and nums[i] == nums[i+1]:    # 去重
                        i += 1
                    i += 1
                    while i < j and nums[j] == nums[j-1]:    # 去重
                        j -= 1
                    j -= 1
        return res

• 时间复杂度：
• 空间复杂度：

240. Search a 2D Matrix II

看成**BST**，从根节点（二维数组右上角）开始搜索，利用双指针和缩减搜索空间。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1
        while i < m and j >= 0:
            if matrix[i][j] < target:
                i += 1
            elif matrix[i][j] > target:
                j -= 1
            else:
                return True
        return False

• 时间复杂度：
• 空间复杂度：

283. Move Zeroes

作为遍历指针，指向非零子数组的末尾元素后方，不断交换和达到移动的目的。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        i = 0
        for j in range(len(nums)):
            if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

• 时间复杂度：
• 空间复杂度：