题目 思路 这道题的难点就在于要求时间复杂度为$O(n)$，空间复杂度为$O(1)$。根据题目可知我们要找到的数必定在区间 $[1, len + 1]$里，当且仅当 $1$ 到 $len$ 都出现过，要寻找的数才为$len + 1$。所以，我们可以先判断$1$ 到 $len$ 的数是否都出现过了。 由于空间复杂度必须为$O(1)$，所以借用$nums$数组本身来记录$1$ 到 $len$的出现情况，如果$[1, len]$中的某个数 x 出现过，我们就用 $nums[x - 1]$ 这个空间来记录其已经出现过了。最后再遍历 nums 数组，查看哪个正整数没有出现过，即看区间$[1, len]$中的哪个正整数没有出现过，如果 $1$ 到 $len$ 都出现过，那么缺失的第一个正整数就是 $len + 1$。 具体来说，我采用的记录方式为 若区间$[1, len]$中的 x 出现过那么将 $nums[x - 1]$ 变为 $-nums[x - 1]$(注意不要重复处理，比如两次相反就变回正数了)，后续遍历时，遍历到下标为 $i$时，若 $nums[i]$ 为负值，则表明 $i + 1$ 这个值出现过。所以，我们要先处理负值，将数组中的 全部负值 变为 $len + 1$(变为 0 或大于 len的任意数都行)。 代码 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 35 36 37 38 39 40 41 42 43 #include <bits/stdc++.

题目 思路 看到题目说寻找最大和的连续子数组，想到了 「560. 和为 K 的子数组」 中的思路 前缀和。对于任意一个区间$[i, j]$（$i \le j$）来说其和为： $$ sum[i, j] = preSum[j] - preSum[i - 1] $$ 我们的目标是找到一个和最大的连续子数组，即： $$ max(preSum[j] - preSum[i - 1])，j \in [0, nums.size() - 1] $$ 我们只需计算出每一个$preSum[j] - preSum[i - 1]$的值，取其中最大值作为答案。但对$preSum[j]$来说我们需要让其减去每一个$preSum[i - 1]$吗？并不需要，因为我们需要的是差值的最大值，所以只需要用一个变量$preSumMin$来记录最小的$preSum[i - 1]$，然后只需计算每一个 $preSum[j] - preSumMin$，取其中的最大差值为答案即可。 代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: int maxSubArray(vector<int>& nums) { int preSumMin = 0, preSum = 0, ans = -1e5; for (int i = 0; i < nums.

题目 思路 直接暴力法，发现超时，怎么进一步优化呢？每个窗口我们都要从头到尾扫描一遍来寻找最大值，这是耗时所在，因为是寻找最大值，直接想到一种非常适合的数据结构——大根堆，堆顶就是最大值。每往右移动一次，就将新的元素加入堆中，再判断堆顶元素是否在窗口内，如果不是就移除，直到在当前窗口的元素成为堆顶。因为将一个元素加入到堆中的时间复杂度为$O(log n)$，所以算法的时间复杂度为$O(n log n)$。 能不能进一步优化呢？当然可以，在一个窗口中，假设两个元素的下标分别为$i, j$且$i < j$，那么「只要$i$在窗口中，$j$也必定在窗口中」。若$nums[i] < nums[j]$， 那么$nums[i]$必定不可能成为最大值，我们就可以不必存储类似$nums[i]$的值。所以，我们只需要用一个双端队列来存储「在当前窗口中可能在以后成为最大值的值的对应下标」。存储下标是因为我们后续要判断该值是否超过窗口范围。 根据前面的分析可知，该队列中的元素是递增的（因为是从左往后扫描的），元素(下标)对应的值是递减的。每次移动窗口就只需要将新元素与队尾元素对应的值进行比较，如果队尾元素对应的值小于新加元素对应的值，则将其移除（因为其对应的值不可能成为最大值了），不断地进行此项操作，直到队列为空或者新元素对应的值小于队尾元素对应值。 显然，队首元素对应的值就是当前窗口的最大值，但需要注意队首元素是否超过了窗口的范围。 这样我们只需要$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 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq; // 初始化, 即处理第一个窗口中的值 for (int i = 0; i < k; ++i) { // 将不可能成为最大值的移除队列 while (!

题目 思路 直接暴力法，遍历每一个子数组查看其和是否为k，发现会超时。暴力法的时间复杂度为$O(n^2)$，瓶颈在于对于每个 $i$，我们需要枚举所有以$nums[i]$作为结尾的子数组来判断其和是否等于k，这一步是否可以优化呢？当然是可以的，考虑到子数组的连续性特性，可以通过 前缀和 来优化。 前缀和是指数组中从第一个元素到当前元素的和。假设 $pre[i]$ 为 $[0, …, i]$里所有数的和，那么 $pre[i]$ 就是前缀和。有了前缀和我们就可以用其来计算子数组的和, “子数组 [j, i] 的和为k” 就可以转化为以下等式： $$ pre[i] - pre[j - 1] = k $$ 通过变形就可以得到： $$ pre[i] - k = pre[j - 1] $$ 这说明，想要知道以 $nums[i]$ 结尾的和为 $k$ 的连续子数组的 个数 时只要统计在位置$i$之前有多少个前缀和为 $pre[i] - k$的$pre[j]$ 。所以，考虑建立哈希表，以前缀和为key，该前缀和出现次数为value，从左往右边更新哈希表边计算答案，即可在$O(n)$时间内完成此题。 需要注意的是，我们在构造哈希表时需要先插入键值对{0, 1} 且在遍历时必须先判断是否有符合条件的前缀和再往哈希表里记录当前前缀和。 为什么可以从左往右依次更新哈希表？ 因为$pre[i]$的值可以由 $pre[i - 1]$递推而来，即： $$ pre[i] = pre[i - 1] + nums[i] $$ 为什么在构造哈希表时需要先插入键值对{0, 1}? 这是为了处理特殊情况。当我们处理到位置 $i$ 时，我们想要知道的是全部以 $nums[i]$ 结尾的和为 $k$ 的连续子数组的个数，这肯定包括由[0, …, i]组成的连续子数组，它们的前缀和即为 $pre[i]$，如果不先插入键值对{0, 1}就会漏掉 $pre[i] = k$ 这一情况，导致漏算答案。

题目

思路

使用两个指针$l, r$分别指向当前字串的左右边界，通过不断将 r 指针往后移使得子串不断变长，在移动r指针的同时需要判断新增的字符是否已经在窗口中出现了，如果已出现则需要移动l指针来将重复的字符移动出窗口，这样通过一次遍历就能找到无重复字符的最长子串。

代码

题目 思路 接的雨水总量为每个柱子能够接的雨水之和，而每个柱子的接水量计算公式为： $$ 接水量=\min(左右两边最高柱子)−当前柱子的高度 $$ 那么直接新建两个数组 left_max 和 right_max 来存储每个柱子左右两侧的最大高度， left_max[i] 和 right_max[i] 分别表示柱子i左右两侧的最高柱子高度( left_max[i] 从左往右计算， right_max[i] 从右往左计算)，然后再通过遍历计算每个柱子的接水量累加起来即可。 上面的方法时间复杂度和空间复杂度均为$O(n)$。时间已经是最快了，那么空间上还能不能进行优化呢？上面的方法空间耗费主要来自于新建的两个存储数组。由于数组left_max是从左往右计算，数组right_max是从右往左计算，因此可以使用双指针和两个变量代替两个数组。 对于左指针left来说，其左右两侧的最大高度分别为left_left_max和 left_right_max；同理右指针有right_left_max和 right_right_max。由于$right > left$，故$right\_left\_max \ge left\_left\_max$ 且 $left\_right\_max \ge right\_right\_max$，这两个不等式画个图便可直接看出。 由上面的不等式可知： 若$right\_right\_max > left\_left\_max$，则必有$left\_right\_max > left\_left\_max$，又left_left_max是可知的， 那么就可以计算left指向的柱子的接水量。 若$right\_right\_max < left\_left\_max$，则必有$right\_left\_max > right\_right\_max$，又right_right_max是可知的， 那么就可以计算right指向的柱子的接水量。 在处理了left指向的柱子后，++left向右移; 在处理了right指向的柱子后，--right向左移，直到全部柱子都被处理。 代码 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: int trap(vector<int>& height) { int ans, left, left_max; int right, right_max; ans = left = 0; right = height.

题目 思路 题目中要求找到所有 「不重复」且和为0的三元组，这个「不重复」的要求使得无法直接使用三重循环枚举所有的三元组找到答案。当然，可以直接用三重循环枚举每个答案，再使用哈希表进行去重(即先对得到的答案进行排序，比如从小到大，再转化成string后存放进unordered_set)，得到最终答案。这种做法时间复杂度和空间复杂度都很高，因此需要换一种思路来考虑这个问题。 重复的答案形式为：$(a, b, c)、(a, c, b)、(b, a, c)$…… 假设$a \le b \le c$，如果能保证只有$(a, b, c)$这种形式的答案会被枚举，就能够直接去除掉重复的答案，而不必再使用哈希表来进行去重了。 要实现这一点，就可以通过将数组中的元素从小达到进行排序，随后使用三重循环进行遍历，且 「每重循环相邻两次枚举的元素不能相同」，否则也会造成重复。例如：一个排完序后的数组为$[-1, 0, 1, 1, 2, 3]$，第一次枚举到的三元组为$(-1, 0, 1)$ ，如果第三重循环继续枚举下一个相邻元素，那么仍然为 $(-1, 0, 1)$，这就产生了重复，因此就需要将第三重的循环跳到下一个不相同的元素，即数组中的最后一个元素3，枚举三元组$(-1, 0, 3)$。 至此，我们已经对初始版本进行了空间上的优化，下面给出伪代码： 1 2 3 4 5 6 7 8 9 10 nums.sort() for first = 0 .. n-1 // 只有和上一次枚举的元素不相同，我们才会进行枚举 if first == 0 or nums[first] != nums[first-1] then for second = first+1 .. n-1 if second == first+1 or nums[second] !