0209._Minimum_Size_Subarray_Sum

发表于 分类于 ， ，

209. Minimum Size Subarray Sum

难度: Medium

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

算法来源于知乎文章——趣味算法思想

  • 这里可以看到由于需要找连续的子数组，所以依旧可以设置两个指针，往同一方向移动。
  • 如果两个指针中间的值加起来>sum的时候，记录此时数组的长度，接着左指针移动，减小sum的值 ；
  • 如果< sum的话，右指针移动扩大范围。
  • 最后返回最短的长度值。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number} s
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(s, nums) {
  var left = 0;
  var right = -1; // right 的起始位置很重要，这里选择-1 [left, right]这个区间刚开始是没有值的
  var tmpSum = 0;
  var minLength;

  // 循环停止的条件是左指针小于长度
  while (left < nums.length - 1) {
    if(tmpSum < s) {
      // 这里要注意边界的处理，当右指针移动到最后一个元素的时候结束
      if(right >= nums.length -1) {
        return minLength || 0;
      }
      right ++;
      // 这里tmpSum的计算也很巧妙，直接用累加的方式，节省计算量
      tmpSum = tmpSum + nums[right]
    } else {
      var tmp = right - left + 1;
      if(minLength) {
        if(tmp < minLength) {
          minLength = tmp;
        }
      } else {
        minLength = tmp;
      }
      // 左边指针移动减少sum的值
      tmpSum = tmpSum - nums[left];
      left ++;
    } 
  }
  if(!minLength) {
    return 0;
  }
  return minLength;
};