LeetCode209-长度最小的子数组

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/minimum-size-subarray-sum/

中文链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

题目详述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例: 

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

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

题目详解

  • 运用双指针 l 和 r。
  • l 指向连续子数组的左边界，r 指向连续子数组的右边界的下一个位置，即 [l, r) 为可能的连续子数组。
  • 每次移动 r 直至满足条件，然后更新最结果，使 l 右移，直至区间 [l, r) 不再满足条件。
  • 重复这个过程，继续移动直至结束。
  • 时间复杂度为 O(n)。
  • 空间复杂度为 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00209 {

    public int minSubArrayLen(int s, int[] nums) {
        int res = Integer.MAX_VALUE;
        int l = 0, r = 0;   // [l, r) 为可能的连续子数组
        int sum = 0;
        while (r < nums.length) {
            sum += nums[r++];
            while (sum >= s) {
                res = Math.min(res, r - l);
                sum -= nums[l++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

进阶要求 O(n log n) 时间复杂度的解法，可以运用二分查找。

  • 首先新建一个数组 sum，用来记录数组 nums 的前缀数组和。
  • 遍历 sum，对每一个位置 i，在数组 sum 中找到大于等于 sum[i - 1] + s 的第一个位置 index。
  • 若存在表明找到一个可能的区间 [i, index]，并更新结果。
  • 时间复杂度为 O(n)。
  • 空间复杂度为 O(nlogn)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class LeetCode_00209 {

    public int minSubArrayLen(int s, int[] nums) {
        int res = Integer.MAX_VALUE;
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; ++i) {
            int index = Arrays.binarySearch(sum, sum[i - 1] + s);
            if (index < 0) {
                index = -(index + 1);
            }
            if (index != sum.length) {
                res = Math.min(res, index - i + 1);
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}