LeetCode 209. Minimum Size Subarray Sum [Medium]

发表于 | 更新于 | 分类于 ， | 阅读次数：

题目来源：https://leetcode.com/problems/minimum-size-subarray-sum/

题目难度：Medium

解答1[Java]：

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
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int right = -1;
        int sum = 0;
        int result = nums.length + 1;

        while (left < nums.length) {
            if (right + 1 < nums.length && sum < s) {
                sum += nums[++right];
            } else {
                sum -= nums[left++];
            }

            if (sum >= s) {
                result = min(result, right - left + 1);
            }
        }

        if (result == nums.length + 1) {
            result = 0;
        }

        return result;
    }

    private int min(int a, int b) {
        return a < b ? a : b;
    }
}

思路

left 和 right 之间形成一个动态窗口，每次根据窗口内的元素的和与给定的数字作比较，确定是收缩窗口还是向右扩大窗口。