长度最小的子数组

发表于 更新于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，209. Minimun Size Subarray Sum

先看题目描述

大意就是给定一个数组 nums 和一个正整数 s，返回满足元素之和大于 s 的 nums 子数组的最小长度

算法和思路

思路就是定义2个指针 end 和 start 来表示子数组的开始和结束位置，即子数组 nums[start, end)，用一个变量 sum 来维护子数组之和，变量 res 来维护满足的最小长度，初始状态 start, end, sum均为 0

每一轮迭代，将 nums[end] 加到 sum 并将 end 右移直至 sum >= s 或者 end 超出数组长度，如果 sum < s，则直接跳出迭代，返回此时 res，若 sum >= s，则将nums[start] 从 sum 中减去并将 start 右移，直至 sum < s，此时子数组的的长度为 end - start + 1，在此过程中更新子数组的最小长度。多次迭代后 end 超出数组长度时，返回 res

算法流程

  • 当 end < nums.length时

    • 当 sum < s 且 end < nums.length 时
      • 将 nums[end] 加到 sum，end 右移
    • 若 sum < s，则直接跳出迭代
    • 当 sum >= s 时
      • 将 nums[start] 从 sum 中减去，start 右移
    • 此时子数组长度为 end -start + 1，更新子数组最小长度 res

  • 返回 res

算法源码

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) {
        if (nums.length == 0) return 0;
        int res = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        int sum = 0;
        while (end < nums.length) {
            while (sum < s && end < nums.length) {
                sum += nums[end]; 
                end++;
            }
            if (sum < s) break;
            while (sum >= s) {
                sum -= nums[start];
                start++;
            }
            res = Math.min(res, end - start + 1);
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}