这道题有很多种方法，我们可以记录下所有的1对应的位置，然后计算所有和为S的子数组。比如对于数组[1,0,1,0,1]，其1所在的位置为[0, 2, 4]。那么S等于2的时候:
- [0, 2-3]满足条件
- [1-2, 4]满足条件
每次我们check 区间和等于S的可能的子区间的左边界和右边界的范围，从最左边满足条件的位置开始，一步一步向右边计算即可。时间空间复杂度均为O(N)，代码如下:
另一种方法就是presum，每次我们看有多少前缀和等于currPreSum - S的即可。时间空间复杂度均为O(N)，代码如下:
我们还有一种不需要额外空间的解法，就是双指指针。但是这里只有两个指针是不够的，对于以j结尾的数组，我们还需要另外两个指针:
- lo表示[lo, j]的和等于S的最小index
- hi表示[hi, j]的和等于S的最大index
这样每次对于j结尾的子数组，满足条件的有hi - lo +1个。时间复杂度O(N)，常数空间，代码如下:
No comments:
Post a Comment