双指针
15. 三数之和
给你一个整数数组 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-105 <= nums[i] <= 105
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
//要求返回数字而非下标，可以无需引入副本，直接对原数组排序
sort(nums.begin(), nums.end());
//剪枝：排序后第一个元素大于 0，必不可能存在三数之和等于 0
if(nums[0] > 0) return res;
//只有两数之和可以用双指针，三数之和要在两数之和外部套一层遍历
//要预留用双指针处理的两数之和，所以外部第 n 层被遍历的元素不能超过原数组长度 -(n - 1)
for(int i = 0; i < nums.size() - (3-1); i++){
//剪枝：重复的直接跳过，无需做后续处理
if(i>0 && nums[i] == nums[i-1]){
continue;
}
//内部复用两数之和的逻辑，但是左指针为外层遍历元素的下一个数，即 i + 1
int left = i + 1;
int right = nums.size() - 1;
while(left < right){
//如果去重逻辑放在找到第一个三元组之前，则可能直接导致漏掉 [0,0,0] 的情况
if(nums[i]+nums[left]+nums[right]==0){
//返回的不是下标，故可以直接操纵原本
res.push_back(vector<int>{nums[i], nums[left], nums[right]});
//去重逻辑应该放在找到第一个三元组之后
//注意区分内外去重逻辑的差异
//内部去重主要考虑边界问题，所以向前看
//外部去重主要考虑排序问题，所以往回看
while(left < right && nums[right] == nums[right - 1]){
right--;
}
while(left < right && nums[left] == nums[left + 1]){
left++;
}
//找到答案时，双指针同时收缩，因为还要继续搜索
//其实两数之和也应该同时收缩，但是两数之和题目中给明只有一个有效答案，所以当时直接返回
right--;
left++;
}else if(nums[i]+nums[left]+nums[right]>0){
right--;
}else if(nums[i]+nums[left]+nums[right]<0){
left++;
}
}
}
return res;
}
};
42. 接雨水
给定 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 * 1040 <= height[i] <= 105
class Solution {
public:
//双指针，按列求 ↓
int trap(vector<int>& height) {
//剪枝：宽度小于 3，接不到雨水
if (height.size() <3) return 0;
//定义首尾指针
int left = 0, right = height.size()-1;
//定义左右最高柱子高度
int maxLeft = 0, maxRight = 0;
//定义结果
int res = 0;
while(left < right){
// 短板效应合并：下标 i （第 i 列）所能接水的面积，由 maxLeft 和 maxRight 决定
//1. 确定下标 i By 比较 height[left] 和 height[right]
//2-1. 计算下标面积 By maxLeft - height[left]（前提：height[left] < maxLeft）
//2-2. 计算下标面积 By maxRight - height[right]（前提：height[right] < maxRight）
// 短板效应视角一：下标 i 取 left 还是 right，由 height[left] 和 height[right] 决定
if(height[left] < height[right]){
//短板效应视角二：只有内部小于外部，才能接到水
if(height[left] < maxLeft){
res+=(maxLeft - height[left]);
}
//else res += 0;
maxLeft = max(height[left], maxLeft);
left++;
}else{
//短板效应视角二：只有内部小于外部，才能接到水
if(height[right] < maxRight){
res+=(maxRight - height[right]);
}
//else res += 0;
maxRight = max(height[right],maxRight);
right--;
}
}
return res;
}
};
图示
图示源于 leetcode 图解
- 较矮的墙的高度大于当前列的墙的高度：注水量 = 较矮的一边 - 当前列的高度
- 较矮的墙的高度小于当前列的墙的高度：不注水
- 较矮的墙的高度等于当前列的墙的高度：不注水
滑动窗口
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
//无需引入 need 和 valid，因为只要求 window 中不出现重复子串
//伸缩逻辑为：有重复则移出，无重复则移入
unordered_map<char, int> window;
int left = 0, right = 0;
//保证可行解：子串
while(right < s.size()) {
//获取移入字符
char in = s[right];
//移入信号
right++;
//移入执行
window[in]++;
//保证最优解（限制解）：不重复
while(window[in] > 1) {
//获取移出字符
char out = s[left];
//移出信号
left++;
//移出执行
window[out]--;
}
//答案处理
res = max(res, right - left);
}
return res;
}
};
438. 找到字符串中所有字母异位词
给定两个字符串 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 * 104s和p仅包含小写字母
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> res;
//滑动窗口常规初始化
//need：需要满足字符数量的字母及其所需的字符数量
//window：当前窗口中字母对应的字符数量
//valid：已满足字符数量的字母数量
unordered_map<char, int> need, window;
for(char c: p) need[c]++;
int valid = 0;
//快慢指针
int left = 0, right = 0;
while(right < s.size()){
//获取移入字符
char in = s[right];
//移入信号
right++;
//当移入字符为所需字符时，才做移入处理
if(need.count(in)){
//移入处理
window[in]++;
//当移入字母的字符数量满足所需的字符数量时，已满足字符数量的字母数量 ++
if(window[in] == need[in])
valid++;
}
//只有大于 p.size() 才有可能为可行解
while(right - left >= p.size()){
//满足字符数量要求的字母数量等于需要满足字符数量的字母时，记录结果
if(valid == need.size())
res.push_back(left);
//获取移出字符
char out = s[left];
//移出信号
left++;
//当移出字符为所需字符时才做处理
if(need.count(out)){
//当窗口内满足要求的字母数量等于所需要满足要求的字母数量时移出
//移出后满足要求的字母数量--
if(window[out] == need[out])
valid--;
//移出执行
window[out]--;
}
}
}
return res;
}
};
子串
560. 和为 K 的子数组（前缀和）
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
// 前缀和是指从数组的开头到当前位置的所有元素的和
// 利用前缀和可以快速计算出任意子数组的总和
// 记录前缀和出现的次数，key 为前缀和，value 为该前缀和出现的次数
unordered_map<int, int> preSumCount;
preSumCount[0] = 1; // 初始化前缀和为0的计数为1(源于规定，并无实际意义)
int preSum = 0; // 记录前缀和
int count = 0; // 记录f和为k的子数组个数
for (int i = 0; i < nums.size(); i++) {
preSum += nums[i]; // 计算前缀和
if (preSumCount.find(preSum - k) != preSumCount.end()) {
//判断当前的前缀和 preSum 减去 k 是否在之前的前缀和中出现过
//如果出现过，则说明存在一个子数组的和为 k，需要将该子数组的数量累加到 count 中
count += preSumCount[preSum - k];
}
preSumCount[preSum]++; // 更新前缀和的计数
}
return count;
}
}