双指针

双指针法一般用来解决数组和链表等线性数据结构中的一些问题，在数组中一般使用2个下标，在链表中一般是2个指针。双指针中两个指针的位置和移动顺序有多种组合，比如2个指针分别在头部和尾部，分别向中间移动，又或者2个指针在第一和第二个元素逐渐向后移动。本部分先看一下数组中双指针的用法。

Leetcode15. 三数之和

问题概述：从一个数组中找到3个元素相加和为0.

解题思路：首先对数组排序，然后从左到右遍历第一个元素，固定第一个元素后，剩余两个元素分别从下一个位置和最后一个位置向中间移动，直到找到和为0或者相遇。

Python代码：

def threeSum(nums):
    # 排序
    nums = sorted(nums)
    i = 0
    j = 0
    k = 0
    result = []
    # 遍历
    while k < (len(nums) - 2):
        if nums[k] > 0:
            break
        i = k + 1
        j = len(nums) - 1
        while i < j:
            left = nums[i]
            right = nums[j]
            if nums[i] + nums[j] + nums[k] == 0:
                result.append([nums[k], nums[i], nums[j]])
                while j > i and nums[j] == right:
                    j -= 1
                while j > i and nums[i] == left:
                    i += 1
            elif nums[i] + nums[j] + nums[k] > 0:
                while j > i and nums[j] == right:
                    j -= 1
            else:
                while j > i and nums[i] == left:
                    i += 1
        current = nums[k]
        while k < (len(nums) - 2) and nums[k] == current:
            k += 1
    return result

LeetCode16. 最接近的三数之和

LeetCode18. 四数之和都和本题类似。

LeetCode11. 盛最多水的容器

题目概述：给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

解题思路：使用双指针，初始时双指针指向开头和结尾，由于容纳的水量是由
两个指针指向的数字中较小值∗指针之间的距离决定的。由于向中间移动指针距离会变小，所以要想容水量最大必须要点的值变大，因此我们移动较小的值直到找到一个比它大的值求出新的容量。一直移动到两个指针相遇求出最大的容量。

Python代码：

def maxArea(height):
    start = 0
    end = len(height) - 1
    result = []
    while start < end:
        if height[start] < height[end]:
            result.append(height[start] * (end - start))
            start += 1
        else:
            result.append(height[end] * (end - start) )
            end -= 1
        
    return max(result)

下篇文档写一下链表中的双指针。