长度最小的字数组（209）

题目

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

进阶

如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

算法

双指针

快慢指针初始都指向位置0，结束条件是慢指针指向数据结尾

快慢指针指向的数组位置是当前连续子串的首尾，所以字串长度是fast-slow+1

快指针fast向前移动时，在结果中加入fast指向的新值，先移动后运算，所以sum += [++fast]

慢指针slow向前移动时，在结果中减去slow移动前指向的值，先运算后移动，所以sum -= [slow++]

每一轮循环我们根据当前sum和s的关系判断移动哪一个指针，当sum>=s的时候我们在移动指针前获取一次当前符合条件的字串的长度

需要注意的是，当快指针指向尾部时，如果sum<s（即不满足慢指针移动的条件时，快指针也因为指向尾部不移动，就会造成死循环），我们移动慢指针只会让值更小，我们可以直接返回结果

export const minSubArrayLen = (s, nums) => {
	let slow = 0,
		fast = 0;
	let minLen = +Infinity;
	let sum = nums[0];
	while (slow < nums.length) {
		if (sum < s) {
			if (fast < nums.length - 1) sum += nums[++fast];
			else return minLen === Infinity ? 0 : minLen;
		} else {
			minLen = Math.min(minLen, fast - slow + 1);
			sum -= nums[slow++];
		}
	}
	return minLen === Infinity ? 0 : minLen;
};

二分查找

我们首先需要维护一个表示前n项和的数组sums，因为题目条件：一个含有 n 个正整数的数组，所以可以保证数组sums一定是递增的，故我们可以使用二分查找。数组sums中sums[i]表示前i个数字的和，所以sums[0]===0且sums.length===nums.length+1

在前n项和的数组sums中，两个位置相减的差，正是对应参数nums中的一个子串的和，比如sums[m] - sums[n]表示nums[n+1]（子串最小值）到nums[m]（子串最大值）这个字串的所有元素的和

那么我们首先需要一个循环来确定上面例子中的sums[m]，因为我们sums[0]表示前0个元素的和，所以我们从sums[1]开始遍历（也就是确定每一轮循环的子串的最大值），之后我们就需要找到sums[n]（子串的最小值）并判断子串和与参数s的关系，因为sums是个递增数组，我们就可以使用二分查找来寻找这个n

二分查找的条件是当sums[i] - sums[mid] < s时，即这个字串的和小于参数s，我们需要让子串有更多的元素（让子串和更大），在子串最大值确定的情况下，我们要扩大子串的和只能缩小字串的最小值，所以我们要向左查找子串最小值，即将end收缩到mid-1；相反地，当我们需要缩小字串和的时候就向右去查找字串的最小值，即将start缩小至mid+1

最后我们利用min===Infinity来判断这个最小子串存不存在，如果存在返回长度；否则返回0

export const minSubArrayLen = (s, nums) => {
	const sums = [0];
	nums.reduce((acc, cur) => {
		acc += cur;
		sums.push(acc);
		return acc;
	}, 0);
	let minLen = +Infinity;
	for (let i = 1; i < sums.length; i++) {
		let start = 0,
			end = sums.length - 1;
		while (start <= end) {
			const mid = ~~((start + end) / 2);
			if (sums[i] - sums[mid] < s) {
				end = mid - 1;
			} else {
				minLen = Math.min(minLen, i - mid);
				start = mid + 1;
			}
		}
	}
	return minLen === Infinity ? 0 : minLen;
};