数组中的双指针解法，链表中快慢指针的解法放到链表专题。
| 题目 | 描述 |
|---|---|
| Leet 11 盛最多水的容器 | 壁高序列注水问题 |
| Leet 3 无重复字符的最长子串 | 经典的双指针滑动窗口问题 |
| Leet 16 最接近的三数之和 | 三数和问题 |
| Leet 992 K 个不同整数的子数组 | 含有 K 个不同元素的窗口 |
双指针滑动窗口
Leet 3 无重复字符的最长子串，Leet 424 替换后的最长重复字符, Leet 978 最长湍流子数组, Leet 992 K 个不同整数的子数组, Leet 1004 最大连续1的个数 III, Leet 1040 移动石子直到连续 II
常见形式： 右指针不断右移，直到窗口不符合要求，然后开始调整左指针，释放部分窗口左边界以使窗口满足要求，继续移动右指针。
例题、
Leet 3. 无重复字符的最长子串
题目： 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
**题解： ** 我们要求的是滑动窗口的最大长度，通过左右两个指针表示。而窗口内出现的字符也需要一个数据结构进行维护，比较容易想到的是 Set ，但是直觉告诉我们 Set 肯定没有数组高效，除非输入的是 String 之类否则应当尽量减少 Set 和 Map 的使用。加之这道题里只有 char ，至多也就 256 种情况，完全可以用一个数组表示。
如果用 boolean[] 表示，我们发现在右指针发现重复字符，左指针还要继续在右指针搜索过的字符串上进行搜索，显然可以进一步优化。我们不用 boolean 数组，而是 在右指针搜索过程中直接将 字符索引 存到一个 int 数组里 ，然后在一开始将数组初始化为 -1 ，这样当右指针发现重复字符（数组中该位置不为 -1），直接将左指针移到数组该位置记录的索引处就可以了，每个字符只搜索一遍，时间复杂度 O(n) 。
public int lengthOfLongestSubstring(String s) {
int[] set = new int[256];
Arrays.fill(set, -1);
int res = 0, left = -1;
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; ++i) {
left = Math.max(left, set[arr[i]]);
set[arr[i]] = -1;
res = Math.max(res, i - left);
}
return res;
}
Leet 424. 替换后的最长重复字符
题目： 给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
题解： 还是滑动窗口的思路，要维护的是其中每个字符出现的次数。我们有个出现最多的字符，需要关注除它以外所有其它字符个数，这只需要做个减法就能得到，这个数字一旦超过了k，左指针就需要移动了。
出现最多的字符有可能发生变化，但也最多只会变成右指针新找到的字符。
public int characterReplacement(String s, int k) {
int[] set = new int[26];
int res = 0, maxCnt = 0;
int left = 0;
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; ++i) {
// 值得注意的是，随着右指针新取到一个字符c，窗口中出现最多的字符
// 要么不变，要么变成新字符
maxCnt = Math.max(maxCnt, ++set[arr[i] - 'A']);
while (i - left + 1 - maxCnt > k) {
--set[arr[left++] - 'A'];
}
res = Math.max(res, i - left + 1);
}
return res;
}
Leet 978 最长湍流子数组
题目： 当 A 的子数组 A[i], A[i+1], …, A[j] 满足下列条件时，我们称其为湍流子数组：
若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]； 或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。 也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。
输入：[9,4,2,10,7,8,8,1,9]
输出：5
解释：(A[1] > A[2] < A[3] > A[4] < A[5])
题解： 就是求锯齿数组最长长度，发现锯齿断了其实很简单，只需要当前浪和前一浪方向一样（都上升或都下降），最大的问题是前后两个数一样的情况，按题意是不能出现平浪的，因此相等时我们直接让左指针把这个平浪跳过，跳到两个相等数靠右的这个来。
如果 left 就在 right 左边一位（在右指针刚开始走，和出现平浪之后都会发生这种情况），那只要不相等，都是可以取的，顺便更新一下浪的方向。
public int maxTurbulenceSize(int[] arr) {
if (arr.length == 1) {
return 1;
} else if (arr.length == 2) {
return (arr[0] == arr[1]) ? 1 : 2;
}
int left = 0, right = 1;
int res = 0;
boolean goingUp;
for (; right < arr.length; ++right) {
if (left == right - 1) {
goingUp = arr[right] > arr[right - 1];
}
if (goingUp == arr[right] > arr[right - 1] || arr[right] == arr[right - 1]) {
res = Math.max(res, right - left);
left = (arr[right] == arr[right - 1]) ? right : right - 1;
} else {
goingUp = !goingUp;
}
}
res = Math.max(res, right - left);
return res;
}
Leet 930 和相同的二元子数组
题目： 给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。子数组 是数组的一段连续部分。
Example 1:
Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation:
The 4 subarrays are bolded below:
[1,0,1]
[1,0,1,0]
[0,1,0,1]
[1,0,1]
Note:
A.length <= 300000 <= S <= A.lengthA[i]is either0or1.
题解： 首先，这道题是可以通过前缀和来做的。这道题有一个特性，是没有负权值，因此前缀和数组是不严格单调递增的，右指针前进，左指针也必然不会后退。
可以使用两个左端点，代表在给定右端点前提下满足要求的左端点集合。什么要求呢？两个指针到右指针间的和，分别为刚好小于目标和的最左端端点和刚好不大于目标和的最左端点，两点之间的就是满足要求的刚好等于目标的位置。
public int numSubarraysWithSum(int[] nums, int t) {
int n = nums.length;
int ans = 0;
for (int r = 0, l1 = 0, l2 = 0, s1 = 0, s2 = 0; r < n; r++) {
s1 += nums[r];
s2 += nums[r];
while (l1 <= r && s1 > t)
s1 -= nums[l1++];
while (l2 <= r && s2 >= t)
s2 -= nums[l2++];
ans += l2 - l1;
}
return ans;
}
这道题更通用的做法是用前缀和+Map记忆。因为这道题没有负值，可以直接用数组替代Map，每次找从当前位置前缀和中扣掉后等于目标和的位置，找到的都是可选的左指针位置。
public int numWithSum(int[] nums, int t) {
int n = nums.length;
int[] sum = new int[n + 1];
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + nums[i - 1];
}
int[] map = new int[n + 1];
map[0] = 1;
int ans = 0;
for (int i = 0; i < n; ++i) {
int r = sum[i + 1], l = r - t;
if (l >= 0) {
ans += map[l];
}
++map[r];
}
return ans;
}
Leet 992 K 个不同整数的子数组
题目： 给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。
输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
题解： 第一眼看有，求子数组个数，稍微有点像动态规划。用滑动窗口求稍微有点困难，因为要求刚好有k个不同整数的子数组并不是那么方便——问题出在左指针上，左指针我们一般会右移直到满足条件，然而满足条件并不意味着其左侧没有满足条件的子数组了。相反，如果让我们求包含了k个以下整数的子数组，会非常方便——左指针满足条件后，左右指针之间都是满足条件的左指针位置，可以一次性全算上。
因此，我们换个法子，通过一个helper函数求k个以下整数子数组的个数，然后再算一个k-1以下的，相减就是刚好k的了。
如何统计每个整数出现的次数呢？正常应当用Map，这里整数的范围已经给定了，那直接用数组快一些。
public int subarraysWithKDistinct(int[] nums, int k) {
return helper(nums, k) - helper(nums, k - 1);
}
private int helper(int[] nums, int k) {
int n = nums.length, res = 0, left = 0;
int[] numCnt = new int[nums.length];
for (int i = 0; i < n; ++i) {
if (numCnt[nums[i] - 1]++ == 0) {
--k;
}
while (k < 0) {
if (--numCnt[nums[left] - 1] == 0) {
++k;
}
++left;
}
res += i - left + 1;
}
return res;
}
Leet 1040 移动石子直到连续 II
题目： 在一个长度 无限 的数轴上，第 i 颗石子的位置为 stones[i]。如果一颗石子的位置最小/最大，那么该石子被称作 端点石子 。
每个回合，你可以将一颗端点石子拿起并移动到一个未占用的位置，使得该石子不再是一颗端点石子。
值得注意的是，如果石子像 stones = [1,2,5] 这样，你将 无法 移动位于位置 5 的端点石子，因为无论将它移动到任何位置（例如 0 或 3），该石子都仍然会是端点石子。
当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。
要使游戏结束，你可以执行的最小和最大移动次数分别是多少？ 以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves] 。
输入：[6,5,4,3,10]
输出：[2,3]
解释：
我们可以移动 3 -> 8，接着是 10 -> 7，游戏结束。
或者，我们可以移动 3 -> 7, 4 -> 8, 5 -> 9，游戏结束。
注意，我们无法进行 10 -> 2 这样的移动来结束游戏，因为这是不合要求的移动。
**题解： ** 这道题实际上需要找到一个固定长度为n的滑动窗口，计算处当前窗口中已有数字个数，总个数减去就是最小步数。窗口的左右边界分别是两块任意石头，如果距离超过n则跳过，不超过，就可以看窗口中已有数字个数。
如果窗口内正好有n-1个数字，窗口大小也是n-1则已经连续了，窗外数字无法直接加到两侧，只能移动两次绕一圈来连续，因此要和2比较取小值。其它情况则跟窗口中空位个数进行比较。
public int[] numMovesStonesII(int[] stones) {
Arrays.sort(stones);
int n = stones.length, low = n, i = 0;
for (int j = 0; j < n; ++j) {
while (stones[j] - stones[i] + 1 > n)
++i;
int al_store = j - i + 1;
if (al_store == n - 1 && stones[j] - stones[i] + 1 == n - 1) {
low = Math.min(low, 2);
} else {
low = Math.min(low, n - al_store);
}
}
return new int[]{low, Math.max(stones[n - 1] - stones[1] - n + 2, stones[n - 2] - stones[0] - n + 2)};
}
N-Sum问题的双指针解法
Leet 15 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
提示：
0 <= nums.length <= 3000-105 <= nums[i] <= 105
题解： 因为要用双指针来求解，因此先固定一个最小点i，然后在它的右区间上使用双指针法。
首先进行一个O(nlogn)的排序，也方便跳过重复元素。因为目标是 0 ，所以双指针搜索的目标是 -num[i]。将左右指针分别放到区间的两个端点，根据和与搜索目标 -num[i] 的大小关系，平移左右指针。这个过程中要跳过重复元素。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums.length < 3) {
return res;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; ++i) {
if (nums[i] > 0)
break;
if (i > 0 && nums[i] == nums[i - 1])
continue;
int l = i + 1, r = nums.length - 1;
int target = -nums[i];
while (l < r) {
if (nums[l] + nums[r] == target) {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
++l;
while (l < r && nums[l] == nums[l - 1]) {
++l;
}
--r;
while (l < r && nums[r] == nums[r + 1]) {
--r;
}
} else if (nums[l] + nums[r] < target) {
++l;
} else {
--r;
}
}
}
return res;
}
Leet 16 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3-10^3 <= nums[i] <= 10^3-10^4 <= target <= 10^4
题解： 和上面一题唯一区别是目标和不一定能被满足，取而代之要求最近的三数和。那么只要在三数和基础上维护一个最近距离，每次指针移动前进行一次判定就行了。
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int res = nums[0] + nums[1] + nums[2], dis = Math.abs(res - target);
for (int i = 0; i < nums.length; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
int t = target - nums[i];
int l = i + 1, r = nums.length - 1;
while (l < r) {
int temp = nums[l] + nums[r];
if (temp == t) {
return target;
} else if (temp < t) {
if (t - temp < dis) {
dis = t - temp;
res = temp + nums[i];
}
++l;
} else {
if (temp - t < dis) {
dis = temp - t;
res = temp +nums[i];
}
--r;
}
}
}
return res;
}
Leet 18 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0
输出：[]
提示：
0 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
题解： 先确定前两个位置，再在后半段通过平移确定后两个点的位置。后两个点跟据总和与目标和的大小关系进行移动，先从距离最远的点——j+1 和 length-1 开始，偏大则右指针左移，偏小则左指针右移。
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 4)
return res;
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; ++i) {
if (i > 0 && nums[i] == nums[i - 1])
continue;
for (int j = i + 1; j < nums.length - 2; ++j) {
if (j > i + 1 && nums[j] == nums[j - 1])
continue;
int l = j + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1])
++l;
while (l < r && nums[r] == nums[r - 1])
--r;
++l;
--r;
} else if (sum < target) {
++l;
} else {
--r;
}
}
}
}
return res;
}