双指针题,两个指针i,j,j先一直移直到sum大于给定数s,然后移动i缩小区间直到sum小于s,然后j - i + 1就是我们要找的长度,双指针移动过程中这个数的最大值就是答案。首先对于一个数组里的元素k,指针j有两种情况:
- 不停下经过k
- 从0开始不停下经过k,说明不存在以k结尾的subarray sum大于s
- 在i停下之后再移动j后经过k,说明加上k的区间和依然小于s,那么以k结尾的和大于s的区间长度一定大于之前找到的区间长度(j移动到k至少移动了一位)。
- 停在k,那么我们找的就是一k结尾的区间和大于s的最小区间长度。
所以算法是正确的,时间复杂度O(n),代码如下:
No comments:
Post a Comment