前缀和

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 53 https://leetcode.cn/problems/maximum-subarray/description/ 难度：中等 本题有两种做法，分别是前缀和以及动态规划。 前缀和的做法为维护最小前缀和，答案为当前前缀和减去最小前缀和。 动态规划的转移方程为 \(f[i] = max(f[i-1],0) + nums[i]\)。 时间复杂度：O(n)，其中 n 为 nums 的长度。 空间复杂度：O(1)。仅用到若干额外变量。 ...