双指针法

通过一个快指针和一个慢指针在一个for循环下完成两个for循环的工作。

其中快指针会遍历整个数组，而慢指针则会遍历一部分数组。主要用于移除数组中的特定数据。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

其中fast指针会遍历整个数组，当该数为非移除项时，则slow会+1并复制该元素。否则，slow不变。

此函数在使用过程汇总，slow的值则会返回数组的长度。数组的传递为地址传递。

我们用慢指针来表示已保存的数组。

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

当数组有序后，我们给定第一个数的情况下，那么，剩下两个数就可以通过left和right指针遍历获得。

对于一个排序的数组，当以第一个为点时，寻找其他两个点大概如下：

以第一个点，设定target为-nums[first]（第一个点的index）
- 当nums[first]大于0，那么说明后面的数都是大于0，此时，三个正数相加结果为正，不符合题目要求
当nums[first]小于0，那么后面的数就可以看是遍历。
此时，在遍历中可以得知，left向右走，则三数之和增大，right向左走，三数之和减少。
- 根据此情况，我们对left加一与right减一并与target进行比较，并调整left和right的位置。

其中需要注意以下的事情：

当数组长度小于3时，表明该数组是无法凑成任何一个三元组的
由于相同元素的可以形成重复的三元组，因此相同的元素会在访问时排除，这是因为三元组要不重复，因此代码里面有nums[i] == nums[i-1]时continue或left++。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if(nums.length < 3)
            return ans;
        int left, right;
        int target;
        for(int i=0; i<nums.length-2; i++){
            if (nums[i] > 0 || i >= 1 && nums[i] == nums[i-1]) {
                continue;
            }
            left = i + 1;
            right = nums.length - 1;
            target = -nums[i];
            while(left != right) {
                while (left < right && nums[left] + nums[right] < target) {
                    left++;
                }
                while (left < right && nums[left] + nums[right] > target) {
                    --right;
                }
                if(left == right){
                    break;
                }
                if(target == nums[left] + nums[right]){
                    List <Integer> _ans = new LinkedList<Integer>();
                    _ans.add(nums[i]);
                    _ans.add(nums[left]);
                    _ans.add(nums[right]);
                    ans.add(_ans);
                    for(; left < right;){
                        if(nums[left] != nums[++left])
                            break;
                    }
                }
            }
        }
        return ans;
    }
}

滑动窗口

不断调整子序列的起始位置和终止位置，从而得出想要的结果。

这也是双指针法的一种，不过这种解法更像一个窗口的移动。

其通过不断调整子序列的起始位置和终止位置，从而将 $O (n^{2})$ 的时间复杂度降为 $O (n)$ 。

寻找最小的子数组 (leetcode no.209)

我们采用两个point，分别为fast和slow，fast会在slow的前面。当fast遍历到和大于等于target时停下，此时对slow进行移动，移动到和小于target时停下。

最终，当slow移动到最右边（slow==len(nums)）时停下。

为了加快计算，我们用个val来表示从slow 到fast这一段数组的和，即sum(nums[slow: fast+1])。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 找出满足和大于等于target的长度最小的连续子数组
        slow, fast = 0, 0
        ans = 0
        val = 0
        while slow != len(nums):
            if val < target and fast != len(nums):
                val += nums[fast]
                fast += 1
                continue
            # print("val = {}, fast = {}, slow =  {}".format(val, fast, slow))
            tmp = fast - slow 
            if (val >= target) and (tmp < ans or ans == 0):
                # print("fast = {}, slow = {}".format(fast, slow))
                ans = tmp
            val -= nums[slow]
            slow += 1
        return ans

水果成篮 (leetcode no.904)

这道题的整体思路与滑动窗口一致，其中具体的思路如下：

通过判定是否满足约束条件来收缩slow，收缩到哪里通过一个记录（以last_exist_idx）进行运算。
- 当水果里面的篮子有3种水果时，我们会把idx最小的水果丢弃，因为后面可能有这种类型的水果加入
```
  fruit_id = knapsack[0]
  idx = last_exist_idx[fruit_id]
  for i in range(1, len(knapsack)):
  	if last_exist_idx[knapsack[i]] < idx:
          fruit_id = knapsack[i]
          idx = last_exist_idx[fruit_id]
      knapsack.remove(fruit_id)
      slow = idx + 1
```
- 这个也是这道题的重点，slow需要移动在哪里停下
fast向前移动，并且需要记录篮子中的水果种类（以knapsack表示）

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        ans = 0
        slow = 0
        length = len(fruits)
        knapsack = []
        last_exist_idx = {}   # used for updating slow
        for fast in range(length+1):
            # update ans
            tmp = fast - slow
            if tmp > ans and len(knapsack) <= 2:
                ans = tmp
            if fast == length:
                break
            # add fruit to knapsack
            if fruits[fast] not in knapsack:
                knapsack.append(fruits[fast])
            # update idx
            last_exist_idx[fruits[fast]] = fast
           	# update slow
            while len(knapsack) > 2:
                fruit_id = knapsack[0]
                idx = last_exist_idx[fruit_id]
                for i in range(1, len(knapsack)):
                    if last_exist_idx[knapsack[i]] < idx:
                        fruit_id = knapsack[i]
                        idx = last_exist_idx[fruit_id]
                knapsack.remove(fruit_id)
                slow = idx + 1
        return ans

最小覆盖子串 (leetcode no.76)