Saturday, September 2, 2017

[LeetCode]Minimum Size Subarray Sum


双指针题,两个指针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