其实，这道题一上来考虑并不是双指针的解法，最 intuitive 的应该是使用 set 或者 dic，因为可以根据条件快速找到符合条件的元素。在使用字典时，有一个 tricky point，就是需要搞清楚什么是 key，什么是 value，这将影响到最后的返回值。我在一开始写这道题的时候并没有想清楚，导致写反了，后面才发现，导致代码没有一次通过，值得反思。给出的解法是基于set的。

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        dic = {}
        for i ,num in enumerate(numbers):
            if target - num in dic:
                return [dic[target - num]+ 1,i + 1]
            dic[num] = i

很快我便想到了可以使用double pointers，从空间上来说，double pointers更加高效，实现也非常简单。

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

这道题也是很有趣，由于长时间没有做题，我的第一反应是dp，但是仔细一想便觉得dp应该是完全不可能的，因为他的父问题本质上没有办法拆分为子问题，即使定义了状态，状态转移方程也不易构建。其次dp的时间复杂度可能达到 O(n²)。所以马上就想到了用贪心算法来实现double pointers，实现也是非常简单。我们在一开始将双指针初始化于数组两端的，确保初始时容器的宽度最大。随后，每次移动较短板对应的指针，尝试找到更高的板，增加容器的高度，从而可能增加容量。这种策略在每一步都做出局部最优选择，最终达到全局最优解。这种方法通过在每一步选择当前最优解，期望最终获得全局最优解。

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