LeetCode 560 https://leetcode.cn/problems/subarray-sum-equals-k/description/ 难度：中等 本题是前缀和题目。需要注意只有满足单调性的时候才能使用滑动窗口。 s 为前缀和，如果 i 到 j 的和为 k，那么 s[j] - s[i] == k。 枚举右，维护左，通过哈希表统计有多少 s[i] == s[j] - k。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(n)。 ...
LeetCode 112 https://leetcode.cn/problems/path-sum/description/ 难度：简单 直接递归调用 hasPathSum，当前节点为叶子节点时判断是否存在路径。 时间复杂度：O(n)，其中 n 为二叉树的节点个数。 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。 ...
LeetCode 179 https://leetcode.cn/problems/largest-number/description/ 难度：中等 要得到最大数，在开头数值不同时，需要把数值大的数排在前面，那么对于有相同数字开头时，应该怎么排序呢？ 只需要把两个数字转成字符串并拼接起来，看哪个前后顺序更大。 auto cmp = [](const int &a, const int &b) { return to_string(a) + to_string(b) > to_string(b) + to_string(a); }; 时间复杂度：O(nlognlogm)，其中 n 是给定序列的长度，m 是 32 位整数的最大值，每个数转化为字符串后的长度是 O(logm) 的数量级。排序比较函数的时间复杂度为 O(logm)，共需要进行 O(nlogn) 次比较。同时我们需要对字符串序列进行拼接，时间复杂度为 O(nlogm)，在渐进意义上小于 O(nlognlogm)。 空间复杂度：O(logn)，排序需要 O(logn) 的栈空间。 ...
LeetCode 198 https://leetcode.cn/problems/house-robber/description/ 难度：中等 状态转移： f[i + 2] = max(f[i + 1], f[i] + nums[i]); 时间复杂度：O(n)。其中 n 为 nums 的长度。 空间复杂度：O(n)。 ...
LeetCode 152 https://leetcode.cn/problems/maximum-product-subarray/description/ 难度：中等 动态规划，类似 LeetCode 53 最大子数组和。由于负负得正，需要维护以 i 结尾的连续子数组乘积的最大值和最小值。 f_max[i] = max({f_max[i - 1] * x, f_min[i - 1] * x, x}); f_min[i] = min({f_max[i - 1] * x, f_min[i - 1] * x, x}); 时间复杂度：O(n)，其中 n 是 nums 的长度。 空间复杂度：O(n)。 ...
LeetCode 62 https://leetcode.cn/problems/unique-paths/description/ 难度：中等 基础的网格图 DP。 时间复杂度：O(mn)。 空间复杂度：O(mn)。 ...
LeetCode 662 https://leetcode.cn/problems/maximum-width-of-binary-tree/description/ 难度：中等 这道题类似二叉树层序遍历，但是除了要保留节点本身，还需要保留节点在本层的编号。对节点 i，左儿子为 2 * i，右儿子为 2 * i + 1。 另外，由于最大 3000 个节点，如果是一条只有右儿子的链，那么编号会达到 \(2^3000\)，任何数据类型都会溢出，所以我们需要使用 unsigned long long 类型，当溢出后会重新回到 0，而不会报错。 时间复杂度：O(n)，其中 n 是二叉树的节点个数。需要遍历所有节点。 空间复杂度：O(n)。广度优先搜索的空间复杂度最多为 O(n)。 ...
LeetCode 113 https://leetcode.cn/problems/path-sum-ii/description/ 难度：中等 子集型回溯。 时间复杂度：\(O(n^2)\)，其中 n 是二叉树的节点个数。对于「一条链 + 完全二叉树」这样的「扫帚型」二叉树，我们会在 O(n) 个叶子节点处，都去复制长为 O(n) 的 path，所以总的时间复杂度为 \(O(n^2)\)。 空间复杂度：O(n)。返回值不计入。 ...
LeetCode:695 https://leetcode.cn/problems/max-area-of-island/description/ 难度：中等 网格图 DFS，类似 LeetCode 200 岛屿数量，增加一个当前岛屿面积的计算。 时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。 空间复杂度：O(mn)。最坏情况下，递归需要 O(mn) 的栈空间。 ...
LeetCode 162 https://leetcode.cn/problems/find-peak-element/description/ 难度：中等 如果 nums[mid] > nums[mid + 1]，说明 mid 要么就是峰值，要么在峰值的右侧，染成蓝色，否则 mid 在峰值的左侧，染成红色。 二分开区间为 (-1, n - 1)。因为 n - 1 一定满足条件，是蓝色。 时间复杂度：O(logn)，其中 n 为 nums 的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...