echo

任生命穿梭 时间的角落

0%

长度最小的子数组

Posted on In Valine:

209. 长度最小的子数组

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

示例: 

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

方法一：暴力法

我们直接枚举子数组的起始点和结束点，计算子数组的和，求解答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length, ans = Integer.MAX_VALUE;
        if(n == 0){
            return 0;
        }

        for(int i = 0; i < n; i++){
            int sum = 0;
            for(int j = i; j < n; j++){
                sum += nums[j];
                if(sum >= s){
                    //更新最小长度
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }
        // 无答案时返回 0 
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

时间复杂度O(n^2)，空间复杂度O(1)。

方法二：双指针

在方法一中我们有许多重复计算，我们使用两个指针 start 和 end ，它们都初始化为 0 ，定义 sum 为子数组 nums[start … end] 的和，每一次迭代将 nums[end] 加到 sum ，当 sum >= s 时更新子数组的最小长度，然后将 nums[start] 从 sum 中减去并将 start 右移，直到 sum < s，重复以上步骤，直到 end 遍历到数组末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length, ans = Integer.MAX_VALUE;
        if(n == 0){
            return 0;
        }
        int start = 0, end = 0, sum = 0;
        while(end < n){
            sum += nums[end];
            while(sum >= s){
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                ++start;
            }
            ++end;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

时间复杂度O(n^2)，空间复杂度O(1)。