leetcode 209. 长度最小的子数组

题目：

209. 长度最小的子数组

题目描述：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

我的思路：

这道题目暴力破解法会超时，使用双层 for 循环进行暴力破解，就是枚举的思想。时间复杂度 O(n*n)。

滑动窗口的思想，也就是双指针，不过是同向双指针，看两边界之间的和是否大于目标值，如果大于等于的话右移左边界，小于的话右移右边界，每次大于等于的时候记录两个边界的距离，和之前最小的进行对比。

/**
 * 暴力破解法，双层 for 循环，判断每一层的个数，暴力破解在 leetcode 会超出时间限制
 *
 * @param target 目标值
 * @param nums   数组
 * @return 最小连续子数组的长度
 */
public int minSubArrayLen(int target, int[] nums) {
    int result = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = nums[i];
        if (sum >= target) {
            result = Math.min(result, 1);
        }
        for (int j = i + 1; j < nums.length; j++) {
            sum += nums[j];
            if (sum >= target) {
                result = Math.min(result, j - i + 1);
                break;
            }
        }
    }
    return result == Integer.MAX_VALUE ? 0 : result;
}

/**
 * 使用滑动窗口看看，滑动窗口也算是双指针的使用
 * @param target 目标值
 * @param nums   数组
 * @return 最小连续子数组的长度
 */
public static int minSubArrayLen2(int target, int[] nums) {
    // 左边界
    int left = 0;
    // 右边界
    int right = 0;
    // 滑动窗口内的所有数之和
    int sum = nums[0];
    // 滑动窗口之间的距离
    int result = Integer.MAX_VALUE;
    while (left <= right && right < nums.length ) {
        // 大于右移左边界
        while (sum >= target && left <= right) {
            result = Math.min(result, right - left + 1);
            sum -= nums[left];
            left ++;
        }
        // 小于右移右边界
        while (sum < target && left <= right && ++ right < nums.length) {
            sum += nums[right];
        }
    }
    return result == Integer.MAX_VALUE ? 0 : result;
}