Prefix Sum
1 | class Solution { |
需要注意的是,使用前缀和数组的潜在条件为数组中的元素不能为负数,若含有负数则不能保证前缀和的单调递增特性,此时不能使用二分搜索。同时注意需要有包含 0 个元素的前缀和,否则 [1, 2, 3, 4, 5]
这样的数组在寻找 target = 15
时就无法找到子数组。
Sliding Window
1 | class Solution { |
Reference
209. Minimum Size Subarray Sum
剑指 Offer II 008. 和大于等于 target 的最短子数组