滑动窗口感觉可以归入双指针一类中
- 用两个指针（left、right）维护一个“当前窗口”，在原序列上线性移动；
- 随着 right 向右扩展，窗口包含的元素增多；当窗口不满足条件时，通过移动 left 收缩窗口；
- 每个元素最多被右指针加入一次、被左指针移出一次，时间复杂度通常为 O(n)。
一、移动零
简单
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]示例 2:
输入: nums = [0]
输出: [0]提示:
1 <= nums.length <= 10^4-2^31 <= nums[i] <= 2^31 - 1
进阶：你能尽量减少完成的操作次数吗？
1.1 向前赋值非0
依旧用l指针保护左侧已处理完的数据，当遇到0时，直接用下一个非0的数据覆盖他（每次会欠1个0）
当r指针走到尽头时，由于l指针左侧保护的是已经处理完的数据（不需要也不能再改动），说明右侧还欠了r - l个0，最后再补回去
或者把nums当成一个栈，用l表示栈的大小，遇到非0的元素就压入，然后把栈的大小l加一，最后把剩余的元素都压入为0
class Solution {
/**
* 283. 移动零（原地栈）
*
* @param nums 提供的数组
*/
public void moveZeroes(int[] nums) {
int length = nums.length, l = 0, r = 0;
for (; r < length; r++) if (nums[r] != 0) nums[l++] = nums[r];
while (l < length) nums[l++] = 0;
}
}执行用时1ms，击败99.99%，复杂度O(N)
消耗内存47.11MB，击败14.15%，复杂度O(1)
1.2 沿途交换0与非0
用l指针隔绝处理完与未处理的数据，保护其左侧已经处理完的数据
l和r每次都一起向右走
用r指针去找右侧未处理数据中可能出现的0，找到了就停下来，跳出当前循环
此时l指向被r跳过的0，当r走到下一个非0时，触发交换，把0换到末尾去
class Solution {
/**
* 283. 移动零（沿途交换0与非0）
*
* @param nums 提供的数组
*/
public void moveZeroes(int[] nums) {
int length = nums.length, l = 0, r = 0;
for (; r < length; r++) {
if (nums[r] == 0) continue;
if (l != r) swap(l, r, nums);
l++;
}
}
private void swap(int l, int r, int[] nums) {
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}执行用时2ms，击败57.92%，复杂度O(N)
消耗内存46.84MB，击败61.40%，复杂度O(1)
二、三数之和
中等
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
2.1 排序 + 双指针
题外话：本题疑似为25年秋招必考题
❓三个数字不能重复，考虑用三个指针，那么如何移动指针
- 当前和 > 0，移动指针使得当前和变小
- 当前和 < 0，移动指针使得当前和变大
但是原数组是无序的，我们并不知道如何移动才能达到预期目的
于是我们可以先从小到大排序数组，如果当前数组最后一个元素比0还小，说明不可能有和为0的三元组，直接返回
固定左边界指针i，不断移动左边界，则问题转化为：我们需要在i的左侧找到和为target = -nums[i]的两个数
❓左右指针l、r的初始位置
如果r = l + 1 = i + 2，操作几次后，当出现和 < 0时，很难判断应该左移l还是左移r
我们期望：
- 其中一个指针的移动必然带来总和的变小
- 另一个指针的移动必然带来总和的变大
由于数组已经从小到大排序，可以定义l = 左边界 + 1，r = 右边界
class Solution {
/**
* 15. 三数之和（双指针）
*
* @param nums 提供的数组
* @return 所有和为0的三元组
*/
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int l, r, target;
int length = nums.length;
List<List<Integer>> ans = new ArrayList<>();
target = Integer.MAX_VALUE;
// 移动左边界
for (int i = 0; i < length - 2; i++) {
if (target == -nums[i]) continue; // 跳过重复数字
target = -nums[i];
l = i + 1; // 只能使总和增大
r = length - 1; // 只能使总和减小
while (l < r) {
int cur = nums[l] + nums[r];
if (cur == target) {
ans.add(List.of(nums[i], nums[l++], nums[r--]));
while (l < r && nums[l] == nums[l - 1]) l++; // 跳过重复数字
while (l < r && nums[r] == nums[r + 1]) r--; // 跳过重复数字
} else if (cur < target) {
l++;
} else {
r--;
}
}
}
return ans;
}
}执行用时32ms，击败85.82%，复杂度O(N^2)
消耗内存58.39MB，击败26.37%，复杂度O(N)
三、盛最多水的容器
中等
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明: 你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。示例 2：
输入：height = [1,1]
输出：1提示：
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4
3.1 贪心 + 双指针
尝试从数组的两端开始往中间收缩，每次收缩的时候只有两种选择：
- 收缩左边界
- 收缩右边界
如果想要出现比当前更大的容纳体积，那么只有收缩小边界才有机会
如果短的板（小边界）不动的话，取到的水永远不会比上次多
class Solution {
/**
* 11. 盛最多水的容器（双指针）
*
* @param height 提供的数组
* @return 最大容纳水的体积
*/
public int maxArea(int[] height) {
int l = 0, r = height.length - 1, s = 0;
while (r > l) {
// 每次尝试缩小短的那条边
s = height[l] > height[r] ?
Math.max(s, (r - l) * height[r--]) :
Math.max(s, (r - l) * height[l++]);
}
return s;
}
}四、无重复字符的最长子串
中等
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示：
0 <= s.length <= 5 * 10^4s由英文字母、数字、符号和空格组成
4.1 滑动哈口
每次循环时判断当前右边界的字符是否已经存在哈希表中
- 如果存在，不断移除左边界的字母直到右边界字符不在哈希表中
不断移动右边界，把遇到的字符都加入哈希表中
class Solution {
/**
* 3. 无重复字符的最长子串（哈希 + 滑动窗口）
*
* @param s 提供的字符串
* @return 最长无重复子串长度
*/
public int lengthOfLongestSubstring(String s) {
if (s == null || s.isEmpty()) return 0;
Set<Character> win = new HashSet<>();
int maxLength = 0;
int l = 0, r = 0;
char[] str = s.toCharArray();
for (; r < str.length; r++) {
while (win.contains(str[r])) win.remove(str[l++]);
win.add(str[r]);
maxLength = Math.max(maxLength, r - l + 1);
}
return maxLength;
}
}五、找到字符串中所有字母异位词
中等
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。提示:
1 <= s.length, p.length <= 3 * 10^4s和p仅包含小写字母
5.1 滑动哈口
此类问题系定长滑动窗口（固定查找p个长度的字符）
由于题目限定小写字母，所以可以定义窗口为int[26]
窗口win记录当前状态的所有字母个数，每次移除左边界字母，加入右边界字母
如果与p中的字母种类及个数相同，加入答案列表中
class Solution {
/**
* 438. 找到字符串中所有字母异位词（哈希 + 滑动窗口）
*
* @param s 提供的字符串
* @param p 目标查询字串
* @return 所有异位字串起始索引
*/
public List<Integer> findAnagrams(String s, String p) {
if (s.length() < p.length()) return new ArrayList<>();
int sl = s.length(), pl = p.length();
int[] win = new int[26];
int[] pc = new int[26];
for (int i = 0; i < pl; i++) {
pc[p.charAt(i) - 'a']++;
win[s.charAt(i) - 'a']++;
}
int l = 0, r = pl - 1;
List<Integer> ans = new ArrayList<>();
if (Arrays.equals(win, pc)) ans.add(l);
while (r < sl - 1) {
win[s.charAt(l++) - 'a']--; // 移除的是当前的，先移除后自增
win[s.charAt(++r) - 'a']++; // 新增的是下一个，先自增后添加
if (Arrays.equals(win, pc)) ans.add(l);
}
return ans;
}
}六、接雨水
困难
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2：
输入：height = [4,2,0,3,2,5]
输出：9提示：
n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5
6.1 逐层砍去法（超时）
用左指针贴地向左扫荡，直到撞到黑色实心方块
用右指针贴地向右扫荡，直到撞到黑色实心方块
在这个扫荡过程中被忽略的就是缺少了半边界的水（无法被接住）
左右边界找到之后，定义一个i从左边界往右边界遍历
- 如果当前格子是水（高度为0），答案 +1
- 如果不是水，直接砍掉
像俄罗斯方块一样一层一层砍掉
但是在第321个测试用例中，遇到了一个从1递增到1w5的height数组，直接超时了（接水的格子成阶梯状）
class Solution {
/**
* 42. 接雨水（双指针，暴力TLE版）
*
* @param height 柱子高度数组
* @return 最大接雨水量
*/
public int trap(int[] height) {
int length = height.length;
int l = 0, r = length - 1, res = 0;
while (l < r) {
while (height[l] == 0 && l < r) l++;
if (l == r) break;
while (height[r] == 0) r--;
for (int i = l; i <= r; i++) {
if (height[i] == 0) res++;
else height[i]--;
}
}
return res;
}
}6.2 逐列抽水法（双指针）
在上面的拼夕夕砍一刀中，我们发现，对于一个U形水坑，得砍好多层才能砍完，耗时太长了
如果能直接把中间的一列水抽走呢
对于每个位置 i，它能接多少雨水取决于：
- 左边最高的柱子
- 右边最高的柱子
- 这两个高度中较小的那个（木桶效应）
所以我们只关注较短柱子的长度数值，不关心较长那根柱子到底多长
这是逐层砍去法若干个1相加的等价数学贡献：ans += 侧边短木板长度 - 当前木桶底部高度
class Solution {
/**
* 42. 接雨水（双指针）
*
* @param height 柱子高度数组
* @return 最大接雨水量
*/
public int trap(int[] height) {
int length = height.length;
int l = 0, r = length - 1;
int ans = 0, lmax = height[l], rmax = height[r];
while (l < r) {
if (height[l] < height[r]) { // 找到最短的木板
ans += lmax - height[l++]; // 当前格子上方的一列格子的水全部抽走
lmax = Math.max(lmax, height[l]);
} else {
ans += rmax - height[r--];
rmax = Math.max(rmax, height[r]);
}
}
return ans;
}
}执行用时0ms，击败100.00%，复杂度O(N)
消耗内存46.75MB，击败72.55%，复杂度O(1)
6.3 逐块填水法（单调栈）
要计算的内容涉及到上一个或者下一个更大或者更小的元素，考虑单调栈
- 单调栈即栈顶到栈底的元素都是单调递增 / 单调递减的
- 新入栈的元素在入栈前弹出栈顶所有比他大（或小，具体看单调递增还是递减）的元素
- 直观来看，存储了一个阶梯状的物体
👇直观来看就是用一块一块长方形在填坑
class Solution {
/**
* 42. 接雨水（单调栈）
*
* @param height 柱子高度数组
* @return 最大接雨水量
*/
public int trap(int[] height) {
int ans = 0;
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < height.length; i++) {
while (st.size() > 0 && height[i] >= height[st.peek()]) {
int bottom = height[st.pop()];
if (st.size() == 0) break; // 无法构成 U 形凹槽
int l = st.peek(); // 凹槽的左侧木板
int h = Math.min(height[l], height[i]) - bottom; // 左右两侧的最短木板
ans += (i - l - 1) * h; // 底 * 高
}
st.push(i);
}
return ans;
}
}