有感于最近太摆了，加上各个群天天力扣，打算做做 HOT 100，也算是为了应付下这学期的数据结构。本来打算一天 5 道题，20 天完成来着，后面想了想还是算了吧（x。每完成一个模块就写一写 writeup。

哈希

T1 1. 两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6 输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6 输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

思路：

力扣第一题，典中典。第一次做想到的是先排序再二分， $O(nlogn)$ ，不过看答案后其实可以用哈希来解决。

本质是在一堆数字中找到一个符合要求的数字，很容易想到对原本的数字进行一些预处理，这样可以 $O(1)$ 地进行查询。考虑最简单的双层循环暴力，一层 $n$ 的开销在遍历，另一层 $n$ 的开销在查询。使用哈希预处理就是在查询这一步变成了 $O(1)$ ，实现了优化。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++) {
            auto x = hash.find(target - nums[i]);
            if(x != hash.end()) {
                return {x -> second, i};
            } else {
                hash[nums[i]] = i;
            }
        }
        return {};
    }
};

T2 49. 字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]] 解释：

• 在 strs 中没有字符串可以通过重新排列来形成 "bat"。
• 字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
• 字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:

输入: strs = [“”] 输出: [[“”]]

示例 3:

输入: strs = [“a”] 输出: [[“a”]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

思路

拥有同样字母的归为一类塞在哈希的一个值里面，关键是怎么处理索引呢？

没啥很好的思路，抄的灵神题解：对每一项先拷贝再 sort ，把 sort 结果当作索引，牛

看评论区有一个超级抽象的索引处理方法： a-z 与前 26 个质数建立映射，生成每个单词的 index ，显然对不同的单词互不相同，估计是最优解。不过还得考虑下单词长度和索引会不会溢出，估计不会卡这个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for(auto& x : strs) {
            string idx = x;
            ranges::sort(idx);
            hash[idx].push_back(x); 
        }
        vector<vector<string>> res;
        res.reserve(hash.size());
        for(auto& it : hash) {
            res.push_back(it.second);
        }
        return res;
    }
};

特别注意一下 res 需要用 reserve 方法预分配一下空间。第二个遍历也可以用 cpp 最新最热特性

1
2
3

for(auto& [_, v] : hash) {
	res.push_back(v);
}

T3 128. 最长连续序列

题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1
2

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

1
2

输入：nums = [1,0,1,2]
输出：3

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

思路

自己做没想出来。首先不能排序（复杂度为 $O(nlogn)$ ），关键在于如何处理哈希。这里应该充分应用哈希集合 $O(1)$ 任意查询的优点，即对每一个递增序列开头元素向后查询并更新。多说无益，show the codes.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set(nums.begin(), nums.end());
        int res = 0;
        for (const auto& v : set) {
            if (!set.contains(v - 1)){
                int length = 1;
                int target = v + 1;
                while (set.contains(target)){
                    length++;
                    target++;
                }
                res = max(res, length);
            }
        }
        return res;
    }
};

双指针

T4 283. 移动零

题目

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1
2

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

1
2

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

**进阶：**你能尽量减少完成的操作次数吗？

思路

尽可能减少操作次数必然产生原数组内的覆盖，有两种思路：记录 0 和 非0。如果记录 0 的位置脑子要转一下，不如直接记录 非0 的个数，即原地栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int ptr = 0;
        for(auto x : nums) {
            if(x) {
                nums[ptr++] = x;
            }
        }
        fill(nums.begin() + ptr, nums.end(), 0);
    }
};

T5 11. 盛最多水的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

1
2
3

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

1
2

输入：height = [1,1]
输出：1

提示：

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

思路

暴力 $O(N^2)$ 肯定不行。考虑结果是一个乘积：底 乘 高，不如固定一个变量的走向，使另一个变量反向走向，然后去找最大值。显然底的最大值容易获取——两端，然后双指针操作两个端点，操作端点使得 $min(height)$ 升高，去找最大值， $O(N)$ 复杂度。

代码

做这题正好和朋友聊起来了压行，不赖，就是可读性一坨。

1
2
3
4
5
6
7
8

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size(), res = 0, i = 0, j = n - 1;
        while(i < j) {res = max(res, (j - i) * min(height[i], height[j])), height[i] < height[j] ? i++ : j--;}
        return res;
    }
};

T6 15. 三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8

输入：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：

1
2
3

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

思路

在典中典的力扣第一题两数之和里面，当初就有一个非常朴素的想法：排序然后双指针，去找唯一的 target。但是这个解法时间复杂度是 $O(nlogn)$，不如哈希表解法的 $O(n)$ 时间复杂度。

对于这道换汤也换药的三数之和，如果想用哈希记录，那遍历至少是嵌套的了，似乎不是很轻松。所以我们又回到了双指针解法：

首先也是排序，其次外层遍历固定第一个数，内层我们要去寻找的另外两个数可以用双指针解法在最差 $O(n)$ 下找到答案，这样时间复杂度大概是 $O(n^2)$。

此外，我们还可以考虑一些剪枝操作和特殊情况：由于这道题并不是让我们找到唯一解，而是找到所有的三元组，因而在第一个元素固定的情况下，如何处理找到一组解后探寻下一祖解。由于不能记录重复三元组，我们让左右指针向中间移动使得与移动前不同。这种情况也适用于外层循环的遍历。

此外，由于我们是排序好的，倘若外层循环已经是整数，则后面两个元素一定也是大于零的，三数之和必然大于零。从最外层遍历到第一个大于零的数时，直接 break 即可。

这道题思路还是能想到的，但是优化细节还是挺繁琐的（x），参考了题解才做出来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        ranges::sort(nums);
        vector<vector<int>> res;
        int n = nums.size(), l, r;
        for(int i = 0; i < n; i++) {
            if(nums[i] > 0)
                break;
            if(i && nums[i] == nums[i - 1])
                continue;
            l = i + 1, r = n - 1;
            while(l < r) {
                if(nums[i] + nums[l] + nums[r] == 0) {
                    res.push_back({nums[i], 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(nums[i] + nums[l] + nums[r] < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return res;
    }
};

T7 42. 接雨水

哎 典中典

题目

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

示例 1：

1
2
3

输入：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：

1
2

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

思路1：双指针记录前后缀最大值

u1s1这题思路是真挺难，做之前早就如雷贯耳了。不过实际做起来还算有意思

考虑一个格子何时是可以放下水的：那就是该格子左侧或者右侧比这一格高度高。进一步说，其实是取决于该格子左侧的最高与右侧最高的最小值减去本格格子高度。

那么似乎很容易想到维护一组双指针，分别去记录前后缀的最大值。考虑到在记录前我们是不得而知某一侧的最大值的，幸运的是我们可以实时的从两侧获取从某一侧开始的最小值。那么思路来了：我们维护两个端点的双指针，始终去向高度低的那一格填水，填完了再向中间移动。这样保证了我们虽然不知道高的那一侧有多高，但是能确保低的那一侧有多低，保证我填水的时总是合法的。左右指针相遇时刻一定在最高的柱子上，显然最高的位置是无法接水的。

有一说一，这个思路挺复杂的，真不太容易想到。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0, prem = 0, sufm = 0;
        int left = 0, right = height.size() - 1;
        while(left < right) {
            prem = max(prem, height[left]);
            sufm = max(sufm, height[right]);
            ans += prem < sufm ? prem - height[left++] : sufm - height[right--];
        }
        return ans;
    }
};

思路2：单调栈

单调栈是一个非常牛逼的数据结构，他的思路其实也很清晰：当我们遍历一个容器时，顺便实时维护一个栈，去记录一组单调递增的元素。

上一种题解的思路是竖着填水，我去寻找每一格的左右侧情况，确保这一格的填入情况。而这个思路是顺着流来从左到右遍历的。同样考虑我们什么时候能确定某个位置能填入水，当且仅当左右侧都比我选中的这个矩形区域高。也就是我们得一直存着这个元素前面比他大的元素，当我们找到下一个比这个元素大的元素时，就可以在中间的矩形填水了，这时弹出中间这个小一点的元素。继续往后找中间的低谷。这就类似于去寻找 “凹” 形，再把 “凹” 填满中间。这样当遍历到最后时，栈内元素一定是单调递增的。同时，我们在填一个低谷时，还需要参考上一个大元素，这和栈的性质不谋而合，很自然（并没有）地想到了单调栈。

维护一个单调栈，不断往里面填元素。当填入的元素大于等于栈顶时，说明我们可以填水了。可是能填多少呢？弹出栈顶后，再看看现在的栈顶是多高，取一个最小值就是最高高度，底部高度即是低谷元素的值。至于宽度，我们在栈内维护索引而非值就好了。

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int ans = 0;
        for(int i  = 0; i < height.size(); i++) {
            int h = height[i];
            while(!st.empty() && h >= height[st.top()]) {
                int bottom = height[st.top()];
                st.pop();
                if(st.empty())
                    break;
                ans += (min(h, height[st.top()]) - bottom) * (i - st.top() - 1);
            }
            st.push(i);
        }
        return ans;
    }
};

滑动窗口

T8 3. 无重复字符的最长子串

题目

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

子字符串 是字符串中连续的 非空 字符序列。

示例 1:

1
2
3

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

思路

首先一眼滑动窗口，但是怎么确保字串不包含重复元素呢？维护一个哈希表，当右端点找到了相同元素，左端点使劲离开窗口直到后端点对应的元素个数为 1 就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size(), ans = 0, left = 0;
        unordered_map<char, int> cnt;
        for(int right = 0; right < n; right++) {
            cnt[s[right]]++;
            while(cnt[s[right]] > 1) {
                --cnt[s[left++]];
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

T9 438. 找到字符串中所有字母异位词

题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 1:

1
2
3
4
5

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

思路

统计异位词子串说白了就是找到相同长度下词频是否相同。那就用俩哈希表存一下，一个预处理 s，一个去统计 p 的子串。不是很难，注意一下细节就好。

由于哈希只需要存英文字母，没必要用哈希，我这里用的 array，想更快一点用静态数组都行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        array<int, 26> example, test;
        int n = p.size();
        for(auto&& c : p) {
            example[c - 'a']++;
        }
        for(int right = 0; right < s.size(); right++) {
            test[s[right] - 'a']++;
            int left = right - n + 1;
            if(left < 0)
                continue;
            if(example == test)
                res.push_back(left);
            --test[s[left++] - 'a'];
        }
        return res;
    }
};

字串

T10 560. 和为 K 的子数组

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1
2

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

1
2

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

思路

由于数组内元素可正可负，因此滑动窗口显然是不行的。求一段连续元素的和容易想到前缀和，那这道题翻译一下就是：找到两个前缀和，使得差为 k。欸，这不是我们典中典的力扣第一题吗？哈希表启动！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0, sums = 0;
        unordered_map<int, int> mp{{0, 1}};
        for(auto x : nums) {
            sums += x;
            if(mp.contains(sums- k))
                ans += mp[sums - k];
            mp[sums]++;
        }
        return ans;
    }
};

T11 239. 滑动窗口最大值

题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

1
2

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

思路

看起来是拿一个滑动窗口一遍滑一边去找最大值。维护一个值作为最大值不断更新可行吗？不可行，因为不断有元素退出，不可能方便快捷地更新。对于这种需要找最大值但是不方便维护内容的最佳选择还是 优先队列。可是优先队列只能 pop 掉堆顶元素，怎么判定滑动时元素是否离开堆呢？答案是我们存索引，每次滑动去检查索引是否离开窗口来确定该 top 我们是否要采用。这样需要重新写一下排序规则，或者省事点把把值和索引存成 pair 放进去。

不过优先队列每次存元素都是 $O(logN)$ 的，太慢了！我们有没有 $O(n)$ 时间复杂度内解决的方案的？答案是有的，那就是单调队列。其实实现思路与滑动窗口方案是几乎一样的。我们使用双端队列 deque 来实现：我们在双端队列中存储索引，同时始终保证前端元素大于后端，方法是：每次在后端加入新元素时，检查这个元素是否比队列最后一个元素更大。由于还没进入的元素一定比已经在的元素更晚弹出，所以直接循环弹出后端比该元素小的，直至他找到对应位置。同时处理队列前端，方法仍然是检查索引是否过期，过期即 pop，没过期就存入。这样就能保证在 $O(n)$ 时间复杂度内解决这个问题了。

代码

优先队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;

        auto cmp = [](const pair<int, int> &a, const pair<int, int> &b){
            return a.first < b.first;
        };

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

        for(int i = 0; i < k; i++) {
            pq.push({nums[i], i});
        }

        res.push_back(pq.top().first);

        for(int i = k; i < n; i++) {
            pq.push({nums[i], i});
            while(pq.top().second <= i - k) {
                pq.pop();
            }
            res.push_back(pq.top().first);
        }
        return res;
    }
};

单调队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;

        deque<int> dq;

        for(int i = 0; i < n; i++) {
            while(!dq.empty() && nums[dq.back()] <= nums[i]) {
                dq.pop_back();
            }

            dq.push_back(i);

            if(dq.front() <= i - k) {
                dq.pop_front();
            }

            if(i >= k - 1) {
                res.push_back(nums[dq.front()]);
            }
        }
        return res;
    }
};

T12 76. 最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
3

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

1
2
3
4

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s 和 t 由英文字母组成

思路

很容易想到用滑动窗口的思路去解决。然而，如何去判断要求的字母是否已经满足了？最简单的思路是创建一个哈希（数组）作为参考存好标准值，然后每次用 $O(52)$ 的复杂度去检查是否满足，似乎这样的代码也是满足 $O(m + n )$ 不过 $m$ 的常数大了点。有没有什么更好的办法？

这里摘抄一段评论区的思考方式：

对于涵盖的定义，直觉上的正向思维是：s 的子串中每个字母的出现次数，都大于等于 t中每个字母的出现次数。 方法一就是直接根据这个定义，遍历cnt数组，判断每个字母的出现次数。 而方法二利用了一个高中学到的等价变换。“每个都大于等于” 等价于“没有小于的” 具体就是：s 的子串中没有字母的出现次数小于t中字母的出现次数。 那么就可以使用一个变量less记录s 的子串中有多少个字母的出现次数小于t中字母的出现次数。当这个变量less==0时，即涵盖。

less的变化有两处： 一是初始化时记录t中有多少个不同的字母。 二是滑动窗口过程中： 如果用一个数组cnt[]比较两个字符串中不同字母的出现次数，那么在用滑动窗口遍历的过程中，只有当子串中字母的出现次数从小于变为了等于或者从等于变为了小于这两种临界状态的变化时，才需要修改less。 这两种状态分别对应向右端扩张窗口后cnt[c]从正变为0，左端收缩窗口后cnt[c]从负变为0。

非常牛逼，定义了一个 less 变量，表示还有多少字母没满足出现次数的要求，同时借助 cnt 数组辅助 。初始遍历要求字符串时在统计进入 cnt 的同时记录进入 less，在滑动右端点时统计进入 cnt 数组时注意 cnt 归零即又有一个字符出现次数满足要求，less 减一。当 less 归零时，记录左右端点，然后滑动左端点直至 less 不再为零。如此满足了每次检查都是绝对意义上的 $O(1)$ 复杂度，实现了进一步的优化。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    string minWindow(string s, string t) {
        int cnt[173] = {}, less = 0;
        for(auto c : t) {
            if(cnt[c] == 0) {
                less++;
            }
            cnt[c]++;
        }

        int left = 0, n = s.size(), ansleft = -1, ansright = n;
        for(int right = 0; right < n; right++) { // 滑动右端点
            cnt[s[right]]--;
            if(cnt[s[right]] == 0) {
                less--;
            }

            while(less == 0) {
                if(right - left <= ansright - ansleft) {
                    ansright = right;
                    ansleft = left;
                }
                if(cnt[s[left]] == 0) {
                    less++;
                }
                cnt[s[left]]++;
                left++;
            } // 滑动左端点
        }

        return ansleft < 0 ? "" : s.substr(ansleft, ansright - ansleft + 1);
    }
};

普通数组

T13 53. 最大子数组和

题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2

输入：nums = [1]
输出：1

示例 3：

1
2

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

思路

首先的首先，求连续序列的和首当其冲的是前缀和。我们想要得到的差最大，需要维护一个最小的前缀和，滚动更新先追和差的最大值， $O(n)$ 复杂度即可解决。注意不能是最大前缀和减最小前缀和，因为无法保证两者的相对位置，只有最大前缀和在最小前缀和右侧才能解决。

这道题目还可以分割子问题用动态规划解决。我们考虑第 i 个子问题为以第 i 个元素结尾的子序列最大值。那么分解：以第 k+1 位结尾的连续子数组有两种取值，一种是 k 位结尾的加第 k+1 位，另一种就是第 k 位本身。最开始我理解的是两种情况分别对应第 k+1 位是正是负，仔细想想实则不然。由于我们只需要求最大值，用滚动更新的办法解决即可。

代码

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, sum = nums[0];
        for(auto x : nums) {
            pre = max(pre + x, x);
            sum = max(sum, pre);
        }
        return sum;
    }
};

T14 56. 合并区间

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

1
2
3

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

1
2
3

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路

画图来考虑一下什么情况的区间会合并

那么我们对所有的区间按前端点排序，用 vector 存答案，每次存答案都检查一下是否和前一个区间有重合部分，即检查后区间的前端点是否小于等于前区间的后端点，然后根据后区间的后端点与序列的前端点确定合并情况，整体而言是很ez的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        ranges::sort(intervals);
        vector<vector<int>> res(intervals.begin(), intervals.begin() + 1);
        for(auto i : intervals) {
            int x = i[0], y = i[1];
            auto j = res.back();
            int m = j[0], n = j[1];
            if(n >= x) {
                res.pop_back();
                res.push_back({m, max(y, n)});
            } else {
                res.push_back(i);
            }
        }
        return res;
    }
};

T15 189. 轮转数组

题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
6

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

1
2
3
4
5

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

进阶：

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

思路

法1：后 k 个元素放到前面，前 n-k 个元素放到后面；

法2：前 n - k 个元素翻转，后 k 个元素翻转，全部元素翻转；

法3：stl 竟然有这个方法：

也就是 std::rotate(nums.begin(), nums.end() - k, nums.end()); 直接解决。

代码

法1：

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res(nums.begin() + n - k % n, nums.end());
        copy(nums.begin(), nums.begin() + n - k % n, back_inserter(res));
        nums.clear();
        nums = res;
    }
};

法2：

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

法3：

1
2
3
4
5
6
7
8

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        std::rotate(nums.begin(), nums.end() - k, nums.end());
    }
};

T16 238. 除自身以外数组的乘积

题目

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

示例 1:

1
2

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在 32 位 整数范围内

**进阶：**你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

思路

题目都提示你前缀元素后缀元素在 32 位整数范围内，要把答案写在你脸上了（bushi

最简单的思路是同时维护前缀和后缀，答案数组的每一位都可以通过对应的前缀乘后缀得到。

那么如何实现在 $O(1)$ 空间复杂度内实现呢？同样给了个提示，输出数组不视为额外空间，言下之意原本 $O(n)$ 空间存下来的东西直接输出就好了。那我们只需要维护后缀和，然后用一个元素滚动更新前缀和，直接把原本思路前缀乘后缀的改为滚动更新的前缀和乘进后缀数组内，然后返回后缀数组。哎，小巧思。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int pre = 1, n = nums.size();
        vector<int> suf(n);
        suf[n - 1] = 1;
        for(int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }
        for(int i = 1; i < n; i++) {
            pre *= nums[i - 1];
            suf[i] *= pre;
        }
        return suf;
    }
};

T17 41. 缺失的第一个正数

题目

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

1
2
3

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

1
2
3

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

1
2
3

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

思路

第零反应是用一个哈希表记录出现的数，处理后遍历。可事实上这个方法太臃肿了，开这么大的数组栈直接炸了。那么我们是不是不用开这么大？毕竟只有 nums.size() 个元素。那不如我们就开 nums.size() 这个大小，如果小于 nums.size() 的数字都出现了，那最小未出现的正数就是 nums.size() + 1，反之缺少哪个答案就是哪个。

这样确实保证了时间复杂度是 $O(n)$，那空间复杂度如何实现常数级别？一般来说，实现常数级别的空间都选择对数组进行原地修改，这里执行一个策略：处理第 i 位索引对应的元素时，如果他的大小在 0 到 nums.size() 之间且不在值的索引位置，就和这个位置交换，直至索引与元素值相同。原地处理完数组后，数组内的元素只有两种：在范围内且在对应位置和反之。找到第一个元素和索引不匹配的元素就是我们要的返回值。如果所有元素都匹配，那返回值就是 nums.size() + 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            while(nums[i] > 0 && nums[i] < n && nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for(int i = 0; i < n; i++) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

链表

回归想做 hot100 的初衷了

160. 相交链表

题目

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

• intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
• listA - 第一个链表
• listB - 第二个链表
• skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
• skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

1
2
3
4
5
6

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

1
2
3
4
5

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

1
2
3
4
5

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

• listA 中节点数目为 m
• listB 中节点数目为 n
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果 listA 和 listB 没有交点，intersectVal 为 0
• 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

**进阶：**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？