双指针篇

题目167：数组numbers 已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数target 的两个数。

思路：既然排好序，那就左指针元素加右指针元素，和与目标相比。大了就右指针移动一位来缩小和。小了就左指针移动一位来变大和。

题目1679：每一步操作中，你需要从整数数组 nums中选出和为 k 的两个整数，并将它们移出数组。返回你可以对数组执行的最大操作数。

思路：和上题类似。排序之后，左右指针找和为k的元素对。

题目11：给定一个长度为 n 的整数数组height。有n条垂线，第 i 条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线，接最多的水。整数数组 nums

思路：如果左边更高，那寻找更大面积的方式就是右指针移动，牺牲底边长度去寻找更高的右边。反之亦然。

题目42：给定n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

思路：注意与上题区别，上题柱子不占体积，本题柱子占体积。柱子接雨水，就要知道左边最高的柱子和右边最高的柱子。这题其实用单调栈更合适。

题目283：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

思路：快慢指针。快指针如果碰到0，快指针就先走一步，慢指针不走。如果没有，就交换快慢指针对应的元素，然后快慢一起走一步。

题目75：给定一个包含0 1 2 共 n 个元素的数组 nums ，进行排序，使得相同颜色的元素相邻。

思路：用left, right 两个指针代表0的上界（不含）和2的下界（不含），current 去遍历数组，分别初始化为0， 0， n-1。如果current遇到0，就和left互换值，left上界也前进一位。如果current遇到2，就和right互换值，right的下界也前进一步。遇到1current就前进一步。

但这里需要注意的是，left前进的时候，current也要前进，因为current从左往右遍历，left以左是0，left到current之间是1，这些都是排好序的。right前进的时候，right以右是2. 但right到current之间不是排好序的。

滑动窗口篇

题目209：给定一个正整数数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组，并返回其长度。

思路：初始化窗口的左右边界left right 都等于0. 向右移动右边界直到窗口和大于等于target。储存窗口长度。左移一步左边界，窗口总和减去左边界元素，然后再移动右边界，加入新元素，直到窗口和大于等于target，再记录长度。

题目3：给定一个字符串 s ，请你找出其中不含有重复字符的最长 子串 的长度。

思路：和上题一样的思路。右边界向前移动直到出现重复字符，此时就要删除左边界元素，直到新加入元素非重复。

题目30：给定一个字符串s 和一个字符串数组words。words中所有字符串 长度相同。返回所有串联子串在s 中的开始索引。

s 中的 串联子串 是指一个包含words中所有字符串以任意顺序排列连接起来的子串。

思路：假设单词长度为3，那0， 1， 2 任何一个位置都可能是串联子串的起点。那分别以 i = 0 1 2 去作为起点。双指针 left, right = i, i + word_len. 用 current_freq记录当前窗口的词频，right 每次前进一个单词距离，把新纳入的字符串作为一个词，词频加一。然后当前词频与目标词频比较，词频大了，就left前进一个单词距离，舍弃的字符串部分词频减一。如果窗口长度能达到串联子串的长度，就说明找到了一个。记录left.

题目438：给定两个字符串s和 p，找到s 中所有p 的异位词 的子串，返回这些子串的起始索引。

思路：与上题类似。不过这里只要统计字符频，不用统计词频。而且每次移动一步。更加简单。

。

题目76：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。

思路：还是统计字符频。子串的字符频必须大于等于 t 的字符频。

题目643：给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

思路：长度固定位k，求最大平均数就是求最大和。移动窗口最大和很简单。

题目1456：给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的子字符串中可能包含的最大元音字母数。

思路：固定长度的移动窗口计数，很简单。

题目1004：给定一个二进制数组 nums和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

思路：其实就是滑动窗口中的0不能超过k个。当超过k个的时候，左边界就要向前走，直到排除一个0，才能纳入新的0.

题目1493：给你一个二进制数组nums，你需要从中删掉一个元素。然后返回最长的且只包含 1 的非空子数组的长度。

思路：窗口中最多一个0.和上题一模一样。

题目220：给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。找出满足下述条件的下标对 (i, j)：1. i != j, 2. abs(i - j) <= indexDiff 3. abs(nums[i] - nums[j]) <= valueDiff如果存在，返回 true ；否则，返回 false 。

思路：如果用一般的滑动窗口，每次添加新元素的时候与原有的元素比较差值，那时间复杂度是O(n*k)，通过不了。这里用SortedSet！

这里我们取寻找 num - valueDiff（后面简称N） 在window中的位置。bisect.bisect_left(window, N) 返回的是大于等于N的第一个数的索引。

如果添加在末尾，意味着最大的数也比num小超过valueDiff 。否则，返回的就是第一个大于等于N的数的索引。那这个数位于[num - valueDiff, 正无穷] 的区间。如果这个数和num的差大于valueDiff ， 那也没有其他数能满足要求了。