【算法笔记】4.LeetCode-Hot100-数组专项

1. 和为 K 的子数组(t560)

中等难度，题目示例如下：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。示例 1：输入：nums = [1,1,1], k = 2
输出：2
示例 2：输入：nums = [1,2,3], k = 3
输出：2 

思路分析：这道题求和首先想到用双指针进行遍历枚举，左指针控制循环开始的位置，右指针在左指针的起始位开始向右累计。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();int num = 0;for (int i = 0; i < n; i++){int sum = 0; for (int j = i; j < n; j++){sum += nums[j];if (sum == k) num++;}}return num;}
};

由于两个循环嵌套，算法复杂度为 O($N^2$)

看题解可以用 前缀和 + 哈希表的方式进行优化，思路有点绕，先看代码再理解：

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

对于数组中的任何位置 j，前缀和 pre[j] 是数组中从第一个元素到第 j 个元素的总和。这意味着如果想知道从元素 i+1 到 j 的子数组的和，你可以用 pre[j] - pre[i] 来计算。

用一个 哈希表 来存储每个前缀和出现的次数，可以快速检查某个特定的前缀和是否已经存在，以及它出现了多少次。

如果 pre - k 存在于 Map 中，说明之前在某个点的累积和是 pre - k。由于当前的累积和是 pre，这意味着从那个点到当前点的子数组之和恰好是 k。

2. 滑动窗口最大值(t239)

困难难度，题目示例如下：

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。示例 1：输入：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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7
示例 2：输入：nums = [1], k = 1
输出：[1]

思路：首先想到暴力解法，直接遍历窗口取值，取最大值。

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> max_num_vec;int n = nums.size();for (int i = 0; i < n - k + 1; i++){int max_num = -9999999;for (int j = i; j < i + k; j++){if (nums[j] > max_num) max_num = nums[j];}max_num_vec.push_back(max_num);}return max_num_vec;}
};

测试用例能过，但提交超时，时间复杂度为O(nk)。

查看题解，可以采用优先队列和单调队列的思路。

优先队列的思路：看上面的暴力解法，实际上改进的方向是显而易见的，因为移动窗口每次只移动一个长度，窗口之间相交的部分实际上是重复计算的。因此，可以用某个方式，先在第一步的时候对窗口信息进行遍历计算，之后每次移动时，只需要把窗口最左边的元素剔除，然后将最右边新的元素和窗口内最大元素比较就行了。

这个具体的方式就是优先队列。优先队列（Priority Queue）是一种特殊的队列数据结构，它不同于普通的先进先出（FIFO）队列，而是根据元素的优先级来决定出队顺序。

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();priority_queue<pair<int, int>> q;for (int i = 0; i < k; ++i) {q.emplace(nums[i], i);}vector<int> ans = {q.top().first};for (int i = k; i < n; ++i) {q.emplace(nums[i], i);while (q.top().second <= i - k) {q.pop();}ans.push_back(q.top().first);}return ans;}
};

这个解法创建了一个优先队列，存储值和其下标，本质上是利用优先队列的特性，通过堆顶来存储窗口中的最大值，相当于不用再专门管最大值如何插入了，这个结构内部已经处理好了排序这一步。

这样的时间复杂度是O(nlogn)，因为将一个元素放入优先队列的时间复杂度为 O(logn)。

单调队列的思路：虽然可以通过优先队列能够比较方便的处理，但如果自己构建一个单调队列，时间复杂度可以进一步优化。所谓单调队列，就是包含单调性的队列，比如让队列头到队列尾，值是单调递减的。

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n = nums.size();deque<int> q;for (int i = 0; i < k; ++i) {while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}q.push_back(i);}vector<int> ans = {nums[q.front()]};for (int i = k; i < n; ++i) { while (!q.empty() && nums[i] >= nums[q.back()]) {q.pop_back();}q.push_back(i);while (q.front() <= i - k) {q.pop_front();}ans.push_back(nums[q.front()]);}return ans;}
};

在 deque 中，q.back()用来读取队尾元素，q.pop_back()是将队尾元素剔除，这个队列实际上是为了保证从队首（front）到队尾（back）下标对应的值是递减的，因此，在初始化的时候，如果发现右边(优先级更高)的值大于队尾对应的值，就可以把队尾给丢掉了。

为什么不直接保留最大值，而是保留下标呢，因为在后面滑动的时候，需要根据下标来判断，是否队首元素已经离开窗口范围了，如果离开，需要将其移除。

这样操作省去了排序的步骤，因此时间复杂度降低到O(n)。

3. 最小覆盖子串(t76)

困难难度，题目示例如下：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。示例 1：输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路分析：这道题需要返回最小字串，这个字串是连续的，因此适合用滑动窗口去做，难点在于，这个窗口是不定长的，而且里面的顺序和t不一致。

直接看官方给的题解：

class Solution {
public:unordered_map <char, int> ori, cnt;bool check() {for (const auto &p: ori) {if (cnt[p.first] < p.second) {return false;}}return true;}string minWindow(string s, string t) {for (const auto &c: t) {++ori[c];}int l = 0, r = -1;int len = INT_MAX, ansL = -1, ansR = -1;while (r < int(s.size())) {if (ori.find(s[++r]) != ori.end()) {++cnt[s[r]];}while (check() && l <= r) {if (r - l + 1 < len) {len = r - l + 1;ansL = l;}if (ori.find(s[l]) != ori.end()) {--cnt[s[l]];}++l;}}return ansL == -1 ? string() : s.substr(ansL, len);}
};

在这段代码中，自定义了一个check函数，用来比较两个unordered_map的值是否对应。主体思路是用双指针来控制窗口范围，窗口右边界不断拓展，直到满足条件，满足条件后，开始收缩左边界，找到条件满足的边界点，此时窗口范围就是最小字串。

4. 最大子数组和(t53)

中等难度，题目示例如下：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1]
输出：1示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

思路分析：题目需要计算连续部分的和，因此想到用滑动窗口的方式去做，核心思路是一旦发现前面累计值为负数，就要完全抛弃，重新开始，因为负数会“拖累”后面加入的新值。

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();int l = 0, r;int max_n = nums[0], ans = nums[0]; for (r = 1; r < n; r++){while (l < r && max_n < 0){max_n -= nums[l];l++;}max_n += nums[r];ans = max(ans, max_n);}return ans;}
};

看了下题解，发现不用双指针这么复杂，可以直接取值求和。

class Solution {
public:int maxSubArray(vector<int>& nums) {int sum = 0, maxSum = nums[0];for (int num : nums) {if (sum < 0) sum = 0; // 如果前面的和为负，不如重新开始sum += num;maxSum = max(maxSum, sum);}return maxSum;}
};

这题最好的思路是用动态规划求解，写法无比简洁：

class Solution {
public:int maxSubArray(vector<int>& nums) {int maxSum = nums[0], currSum = nums[0];for (int i = 1; i < nums.size(); ++i) {currSum = max(nums[i], currSum + nums[i]);maxSum = max(maxSum, currSum);}return maxSum;}
};

代码中，currSum 表示「以当前元素为结尾的最大子数组和」，maxSum 表示「全局的最大子数组和」，面对一个新数 nums[i]，只有两种选择：

• 继续扩展前面的子数组：即 currSum + nums[i]；
• 从当前位置重新开始一个新的子数组：即 nums[i]

从这两者中选取最大的就可以了。

5. 合并区间(t56)

中等难度，题目示例如下：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。示例 1：输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2：输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路分析：这道题还是相对简单的，但要注意的是，数组区间重合可能有多种情况，但不重合只有一种情况，因此下面的代码的条件判断是不重合的情况。

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> merge_vec;sort(intervals.begin(), intervals.end());int left = intervals[0][0];int right = intervals[0][1];for (auto interval : intervals){if (right < interval[0]){merge_vec.push_back({left, right});left = interval[0];right = interval[1];}else{left = min(left, interval[0]);right = max(right, interval[1]);}}merge_vec.push_back({left, right});return merge_vec;}
};

6. 轮转数组(t189)

中等难度，题目示例如下：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。示例 1:输入: 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:输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

思路分析：这道题找规律就行了，k = 3，相当于把最后 3 个元素插入到新数组，前面的按顺序往后插入就行了，唯一需要注意的是 k 有可能会大于 nums 的长度，因此需要取模处理。

先学习一下 c++ 中插入的命令：

vector.insert(position, value);               // 插入一个元素
vector.insert(position, count, value);        // 插入 count 个 value
vector.insert(position, first, last);         // 插入一个区间 [first, last)

题解：

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

看了官方题解，还可以通过数组直接翻转去做，但不如插入简单直观好理解。

7. 除自身以外数组的乘积(t238)

中等难度，题目示例如下：

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。示例 1:输入: nums = [1,2,3,4]
输出: [24,12,8,6]示例 2:输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

思路分析：题目要求不能用除法，但用除法显然是挺简单，于是先尝试用除法解了一下，但需要注意的是，对于数组中含0的情况，需要单独分类判断。

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> result(n, 0);int totalProduct = 1;int zeroCount = 0;// 先统计乘积和 0 的数量for (int num : nums) {if (num == 0) {zeroCount++;} else {totalProduct *= num;}}for (int i = 0; i < n; ++i) {if (zeroCount > 1) {result[i] = 0;  // 两个及以上 0，全部为 0} else if (zeroCount == 1) {result[i] = (nums[i] == 0) ? totalProduct : 0;} else {result[i] = totalProduct / nums[i];  // 正常情况，无 0}}return result;}
};

标准解法是采用前后缀乘积，具体思路是通过两个数组分别记录索引 i 左侧所有元素的乘积和右侧所有元素的乘积，对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积。

举个例子：

nums = [a, b, c, d, e]

如果要计算 answer[2]，也就是 c 位置对应的值，应该是

answer[2] = a * b * d * e

左侧乘积就是 a * b；右侧乘积就是 d * e。

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int length = nums.size();// L 和 R 分别表示左右两侧的乘积列表vector<int> L(length, 0), R(length, 0);vector<int> answer(length);// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1L[0] = 1;for (int i = 1; i < length; i++) {L[i] = nums[i - 1] * L[i - 1];}// R[i] 为索引 i 右侧所有元素的乘积// 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1R[length - 1] = 1;for (int i = length - 2; i >= 0; i--) {R[i] = nums[i + 1] * R[i + 1];}// 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for (int i = 0; i < length; i++) {answer[i] = L[i] * R[i];}return answer;}
};

8. 缺失的第一个正数(t41)

困难难度，题目示例如下：

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。示例 1：输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。示例 2：
输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。示例 3：
输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

思路分析：这道题题面意思很明确，难点在于时间复杂度的限制，如果不限制，则先将数组进行排序，则很容易枚举出来。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();int result = 1;sort(nums.begin(), nums.end());for (int i = 0; i < n; i++){while(result == nums[i]){result++;}}return result;}
};

该方法虽然能过，能不满足题目要求，因为时间复杂度超过 O(n) 了。

看官方题解可以采用置换的方式，核心思想是把数放回自己该在的位置。

比如一个正常的按顺序摆列的数组：

nums = [1,2,3,4]

那么1就应该出现在下标为0的位置，2就应该出现在下标为1的位置，以此类推。

因此，得到规律：对于一个正整数 x，如果它在数组范围 [1, n] 之间，那它应该出现在数组下标 x - 1 的位置。

举个例子，对于乱序数组而言：

nums = [3, 4, -1, 1]

3应该出现在下标2，4应该出现在下标3，-1<0不做处理，1应该去下标0，通过置换的方式，把正整数安排到它正确的位置上：

nums = [1, -1, 3, 4]

这样换完之后，就可以直接查询出缺失位。

具体的代码实现形式：

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[nums[i] - 1] != nums[i]) {swap(nums[nums[i] - 1], nums[i]);}}for (int i = 0; i < n; ++i) {if (nums[i] != i + 1) {return i + 1;}}return n + 1;}
};