Leetcode209. 长度最小的子数组

最开始看错题目了，以为数组的顺序可以打乱......

滑动窗口解法还是挺好想的，不过第一次算子数组的和的时候写了一个方法暴力计算，结果超时了；然后想到用一个 sum 增减元素就能算出结果了

    public int minSubArrayLen(int target, int[] nums) {
        int result = nums.length + 1;
        int left = 0;
        int right = 0;
        int sum = nums[0];
        while (left <= right) {
            if (sum < target) {
                right++;
                if (right >= nums.length) {
                    break;
                }
                sum += nums[right];
            } else {
                result = Math.min((right - left + 1), result);
                sum -= nums[left];
                left++;
            }
        }
        return result > nums.length ? 0 : result;
    }

从题解中还学到了一种前缀和 + 二分查找的解题方法，虽然不如滑动窗口法高效，不过也是一种新思路

通过前缀和数组，计算子数组和的原理：

前缀和数组 sums 的每个元素 sums[i] 表示从数组开始到第 i-1 个元素的累积和，即 sums[i] = nums[0] + nums[1] + ... + nums[i-1]。

通过前缀和数组，任意子数组 nums[i] 到 nums[j] 的和可以通过如下方式计算：

这种方法将子数组和的计算复杂度从 O(n) 降低到了 O(1)，因为只需做一次减法运算。