Question

209. 长度最小的子数组

English Version

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

 

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

 

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

 

进阶：

• 如果你已经实现_ _O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解法

方法一：前缀和 + 二分查找

我们先预处理出数组 $nums$ 的前缀和数组 $s$，其中 $s[i]$ 表示数组 $nums$ 前 $i$ 项元素之和。由于数组 $nums$ 中的元素都是正整数，因此数组 $s$ 也是单调递增的。另外，我们初始化答案 $ans = n + 1$，其中 $n$ 为数组 $nums$ 的长度。

接下来，我们遍历前缀和数组 $s$，对于其中的每个元素 $s[i]$，我们可以通过二分查找的方法找到满足 $s[j] \geq s[i] + target$ 的最小下标 $j$，如果 $j \leq n$，则说明存在满足条件的子数组，我们可以更新答案，即 $ans = min(ans, j - i)$。

最后，如果 $ans \leq n$，则说明存在满足条件的子数组，返回 $ans$，否则返回 $0$。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

class Solution:
  def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    n = len(nums)
    s = list(accumulate(nums, initial=0))
    ans = n + 1
    for i, x in enumerate(s):
      j = bisect_left(s, x + target)
      if j <= n:
        ans = min(ans, j - i)
    return ans if ans <= n else 0

class Solution {
  public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    long[] s = new long[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = n + 1;
    for (int i = 0; i <= n; ++i) {
      int j = search(s, s[i] + target);
      if (j <= n) {
        ans = Math.min(ans, j - i);
      }
    }
    return ans <= n ? ans : 0;
  }

  private int search(long[] nums, long x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    vector<long long> s(n + 1);
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
    int ans = n + 1;
    for (int i = 0; i <= n; ++i) {
      int j = lower_bound(s.begin(), s.end(), s[i] + target) - s.begin();
      if (j <= n) {
        ans = min(ans, j - i);
      }
    }
    return ans <= n ? ans : 0;
  }
};

func minSubArrayLen(target int, nums []int) int {
  n := len(nums)
  s := make([]int, n+1)
  for i, x := range nums {
    s[i+1] = s[i] + x
  }
  ans := n + 1
  for i, x := range s {
    j := sort.SearchInts(s, x+target)
    if j <= n {
      ans = min(ans, j-i)
    }
  }
  if ans == n+1 {
    return 0
  }
  return ans
}

function minSubArrayLen(target: number, nums: number[]): number {
  const n = nums.length;
  const s: number[] = new Array(n + 1).fill(0);
  for (let i = 0; i < n; ++i) {
    s[i + 1] = s[i] + nums[i];
  }
  let ans = n + 1;
  const search = (x: number) => {
    let l = 0;
    let r = n + 1;
    while (l < r) {
      const mid = (l + r) >>> 1;
      if (s[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  for (let i = 0; i <= n; ++i) {
    const j = search(s[i] + target);
    if (j <= n) {
      ans = Math.min(ans, j - i);
    }
  }
  return ans === n + 1 ? 0 : ans;
}

impl Solution {
  pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut res = n + 1;
    let mut sum = 0;
    let mut i = 0;
    for j in 0..n {
      sum += nums[j];

      while sum >= target {
        res = res.min(j - i + 1);
        sum -= nums[i];
        i += 1;
      }
    }
    if res == n + 1 {
      return 0;
    }
    res as i32
  }
}

public class Solution {
  public int MinSubArrayLen(int target, int[] nums) {
    int n = nums.Length;
    long s = 0;
    int ans = n + 1;
    for (int i = 0, j = 0; i < n; ++i) {
      s += nums[i];
      while (s >= target) {
        ans = Math.Min(ans, i - j + 1);
        s -= nums[j++];
      }
    }
    return ans == n + 1 ? 0 : ans;
  }
}

方法二：双指针

我们可以使用双指针 $j$ 和 $i$ 维护一个窗口，其中窗口中的所有元素之和小于 $target$。初始时 $j = 0$，答案 $ans = n + 1$，其中 $n$ 为数组 $nums$ 的长度。

接下来，指针 $i$ 从 $0$ 开始向右移动，每次移动一步，我们将指针 $i$ 对应的元素加入窗口，同时更新窗口中元素之和。如果窗口中元素之和大于等于 $target$，说明当前子数组满足条件，我们可以更新答案，即 $ans = \min(ans, i - j + 1)$。然后我们不断地从窗口中移除元素 $nums[j]$，直到窗口中元素之和小于 $target$，然后重复上述过程。

最后，如果 $ans \leq n$，则说明存在满足条件的子数组，返回 $ans$，否则返回 $0$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

class Solution:
  def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    n = len(nums)
    ans = n + 1
    s = j = 0
    for i, x in enumerate(nums):
      s += x
      while j < n and s >= target:
        ans = min(ans, i - j + 1)
        s -= nums[j]
        j += 1
    return ans if ans <= n else 0

class Solution {
  public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    long s = 0;
    int ans = n + 1;
    for (int i = 0, j = 0; i < n; ++i) {
      s += nums[i];
      while (j < n && s >= target) {
        ans = Math.min(ans, i - j + 1);
        s -= nums[j++];
      }
    }
    return ans <= n ? ans : 0;
  }
}

class Solution {
public:
  int minSubArrayLen(int target, vector<int>& nums) {
    int n = nums.size();
    long long s = 0;
    int ans = n + 1;
    for (int i = 0, j = 0; i < n; ++i) {
      s += nums[i];
      while (j < n && s >= target) {
        ans = min(ans, i - j + 1);
        s -= nums[j++];
      }
    }
    return ans == n + 1 ? 0 : ans;
  }
};

func minSubArrayLen(target int, nums []int) int {
  n := len(nums)
  s := 0
  ans := n + 1
  for i, j := 0, 0; i < n; i++ {
    s += nums[i]
    for s >= target {
      ans = min(ans, i-j+1)
      s -= nums[j]
      j++
    }
  }
  if ans == n+1 {
    return 0
  }
  return ans
}

function minSubArrayLen(target: number, nums: number[]): number {
  const n = nums.length;
  let s = 0;
  let ans = n + 1;
  for (let i = 0, j = 0; i < n; ++i) {
    s += nums[i];
    while (s >= target) {
      ans = Math.min(ans, i - j + 1);
      s -= nums[j++];
    }
  }
  return ans === n + 1 ? 0 : ans;
}