【LeetCode Solutions】LeetCode 热题 100 题解（6 ~ 10）

双指针 - LeetCode 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\le nums.length\le 3000$
$-10^5\le nums[i]\le 10^5$

【分析】

先对数列进行排序，为了避免重复，我们规定三个指针 $i<j<k$，我们枚举其中一个指针 $i$，也就是固定 $i$，然后通过双指针算法找出 $j$ 和 $k$。我们让 $j$ 从前往后走，让 $k$ 从后往前走，我们要找出 nums[i] + nums[j] + nums[k] == 0，由于序列是单调递增的，我们将 $k$ 从右往左移动，找到最小的满足 nums[i] + nums[j] + nums[k] >= 0 的 $k$，如果此时不满足等于 0，那么就将 $j$ 向右移，增大这个式子的和，然后再将 $k$ 向左移直到找到最小的满足 nums[i] + nums[j] + nums[k] >= 0 的 $k$，再判断是否等于 0，以此类推。

还有一点需要注意的是枚举 $i$ 或 $j$ 的时候如果 nums[i] 或 nums[j] 和上一个数一样就要跳过（序列是有序的因此和上一个数不一样的话之后也不会再出现之前的数了），防止重复枚举。

【代码】

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for (int i = 0; i < nums.size(); i++) {
            if (i && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1, k = nums.size() - 1; j < k; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                while (nums[i] + nums[j] + nums[k - 1] >= 0 && j < k - 1) k--;
                if (nums[i] + nums[j] + nums[k] == 0) res.push_back({nums[i], nums[j], nums[k]});
            }
        }
        return res;
    }
};

双指针 - LeetCode 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

【提示】

$1\le height.length\le 2\ast 10^4$
$0\le height[i]\le 10^5$

【分析】

本题需要用到单调栈的思想，先画出示意图：

我们开一个栈记为 stk，每根柱子的编号已在图中显示，假设柱子的高度依次为：height = [6, 3, 0, 5, 4, 5, 7]，算法流程如下：

• 栈为空，将 0 入栈（当前栈：[0]）；
• 1 小于栈顶元素，入栈（当前栈：[0, 1]）；
• 2 小于栈顶元素，入栈（当前栈：[0, 1, 2]）；
• 3 大于等于栈顶元素，将小于等于 3 的元素依次出栈，首先出栈 2，若栈里还有元素，则 res += (3 - 1 - 1) * (min(height[1], height[3]) - height[2]) = 3（红色区域），其中 1 为栈顶元素；然后出栈 1，栈不为空，res += (3 - 1 - 0) * (min(height[0], height[3]) - height[1]) = 7（黄色区域）；栈顶元素 0 大于 3，停止出栈，将 3 入栈（当前栈：[0, 3]）；
• 4 小于栈顶元素，入栈（当前栈：[0, 3, 4]）；
• 5 大于等于栈顶元素，将小于等于 5 的元素依次出栈，首先出栈 4，栈不为空，res += (5 - 1 - 3) * (min(height[3], height[5]) - height[4]) = 8（绿色区域）；然后出栈 3，栈不为空，res += (5 - 1 - 0) * (min(height[0], height[5]) - height[3]) = 8（面积为0）；栈顶元素 0 大于 5，停止出栈，将 5 入栈（当前栈：[0, 5]）；
• 6 大于等于栈顶元素，将小于等于 6 的元素依次出栈，首先出栈 5，栈不为空，res += (6 - 1 - 0) * (min(height[0], height[6]) - height[5]) = 13（蓝色区域）；然后出栈 0，栈为空，停止出栈，将 6 入栈（当前栈：[6]），遍历结束。

【代码】

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> stk;
        int res = 0;
        for (int i = 0; i < height.size(); i++) {
            if (stk.empty() || height[i] < height[stk.top()]) { stk.push(i); continue; }
            while (stk.size() && height[i] >= height[stk.top()]) {
                int t = stk.top(); stk.pop();
                if (stk.size())  // 注意判断栈里是否还有元素
                    res += (i - 1 - stk.top()) * (min(height[stk.top()], height[i]) - height[t]);
            }
            stk.push(i);
        }
        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\le s.length\le 5\ast 10^4$
s 由英文字母、数字、符号和空格组成

【分析】

我们枚举所有以 $i$ 为尾端点的子串，分别找出最长的不包含重复字符的子串。因此对于每个 $i$，我们需要找到一个最靠左端点的 $j$，使得 $j\sim i$ 中不包含重复的字符。现在再假设 $i$ 向右移动到 $i^{\prime }$，显然其对应的 $j^{\prime }$ 一定大于等于 $j$，否则通过反证法，$j^{\prime }$ 在 $j$ 的左边且 $j^{\prime }\sim i^{\prime }$ 中不包含重复的字符，那么 $j^{\prime }\sim i$ 中一定也不包含重复的字符。

综上，我们在枚举 $i$ 的时候同样也只需要枚举一遍 $j$，而不需要重复枚举。

【代码】

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> st;
        int res = 0;
        for (int i = 0, j = 0; i < s.size(); i++) {
            st[s[i]]++;
            while (st[s[i]] > 1) st[s[j++]]--;  // 当 j == i 时 s[i] 一定只出现一次了
            res = max(res, i - j + 1);
        }
        return res;
    }
};

滑动窗口 - LeetCode 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\ast 10^4$
s 和 p 仅包含小写字母

【分析】

假设 p 的长度为 $M$，那么我们维护每个长度为 $M$ 的区间，然后用哈希表记录每个区间中各字符的出现次数。

如何快速判断每个区间各字母的出现次数与 p 是相同的？可以维护一个变量 cnt 表示当前区间中有多少种字符满足要求，例如当前区间中 $a$ 出现 2 次，$b$ 出现 1 次，$c$ 出现 2 次，而 p 中有 2 个 $a$、2 个 $b$、1 个 $c$，此时 cnt 就为 1，只有 $a$ 满足要求了，当 cnt 等于 p 中字符的种类数时说明当前区间是答案。

可以只使用一个哈希表，初始先记录 p 中每个字符出现的次数，之后遍历滑动窗口时添加一个字符就在哈希表中将次数减一，如果减为 0 了说明这个字符已经全部出现在 p 中了。

【代码】

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
         unordered_map<char, int> st;
         for (char c: p) st[c]++;
         int tot = st.size();  // p 中字符的种类数
         vector<int> res;
         for (int i = 0, j = 0, cnt = 0; i < s.size(); i++) {
            if (--st[s[i]] == 0) cnt++;  // 当前字符的数量已经与 p 中的一致
            if (i - j + 1 > p.size()) {
                if (st[s[j]] == 0) cnt--;  // 删去 s[j] 后就比 p 中的数量少
                st[s[j++]]++;
            }
            if (cnt == tot) res.push_back(j);
         }
         return res;
    }
};

子串 - LeetCode 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\ast 10^4$
$-1000<=nums[i]<=1000$
$-10^7<=k<=10^7$

【分析】

首先我们从左到右枚举右端点 $i$，然后判断 $i$ 及其左边有多少个左端点 $j$，满足区间 $j\sim i$ 之和为 $k$。

可以用前缀和快速求解，区间 $j\sim i$ 之和即为 $s_i-s_{j-1}$，可以用哈希表记录每个 $s_j$，这样就可以快速获取 $s_j=s_i-k$ 的数量，也就表示在当前的右端点 $i$ 中有多少种符合条件的左端点 $j$。

【代码】

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + nums[i - 1];
        unordered_map<int, int> st;
        int res = 0;
        for (int i = 0; i <= n; i++) {  // 注意边界 s[0] = 0 也要考虑到
            res += st[s[i] - k];
            st[s[i]]++;
        }
        return res;
    }
};