209. 长度最小的子数组

题目链接

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

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

示例 1：

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

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思路

最简单的思路就是双层循环暴力递归了，时间复杂度O(n*n)。一般双层循环的解法都可以使用双指针来进行优化。

双指针(滑动窗口)

使用left、right双指针，先left指针不动，移动right指针直到子数组和大于target，计算当前子数组长度。然后再left指针右移，如果当前子数组和小于target则停止，计算当前子数组长度。然后再left指针右移一位或者right指针右移一位重新开始上述过程。

public int minSubArrayLen(int target, int[] nums) {
	if (target <= 0 || nums == null || nums.length == 0) {
		return 0;
	}

	int right = 0;
	int left = 0;
	int curSum = 0;
	int minLen = Integer.MAX_VALUE;

	while (right <= nums.length && left < nums.length) {

		//移动右指针直到和大于target
		while (right < nums.length && curSum < target) {
			curSum += nums[right++];
		}
		//计算当前子数组长度。由于right++的缘故，此时right指针会多一位，即为子数组有边界的下一位，长度不用再减1
		minLen = curSum >= target ? Math.min(minLen, right - left) : minLen;

		//开始移动左指针，和小于target则停止
		while (left < right && curSum >= target) {
			if (curSum - nums[left] < target) {
				break;
			}
			curSum -= nums[left++];
		}
		//计算当前子数组长度
		minLen = curSum >= target ? Math.min(minLen, right - left) : minLen;

		//如果right指针已到达数组边界，循环终止
		if (right == nums.length) {
			break;
		}

		//left指针右移
		curSum -= nums[left++];
	}

	return minLen = minLen == Integer.MAX_VALUE ? 0 : minLen;
}

代码优化

利用外层循环推动指针移动。

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

结构优化：只需要判断左指针什么时候需要移动即可。

// 滑动窗口
public int minSubArrayLen(int target, int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int left = 0;
    int sum = 0;
    int result = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            result = Math.min(result, right - left + 1);
            // 左指针右移
            sum -= nums[left++];
        }
    }
    return result == Integer.MAX_VALUE ? 0 : result;
}