LeetCode Minimum Size Subarray Sum

LeetCode Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).


给定一个正整数数组和一个数s,要求从数组中找出最短的子串,使得子串的和大于等于s。

解法1,双指针法,O(n)。维护两个指针left和right,初始时都为0,我们的目标就是使[left,right)的和大于等于s。所以先right右移,直到和大于等于s,此时尝试缩小区间,即left也右移,在右移的过程中,更新最短子串长度,且累加和要减去left指向的数。这样不断的先移right,后移left,并更新最短长度。

代码如下,非常简洁易懂。

class Solution {
public:
	int minSubArrayLen(int s, vector<int>& nums) {
		int n = nums.size(), left = 0, right = 0, sum = 0, ans = INT_MAX;
		while(right < n) {
			while (right < n&&sum < s)sum += nums[right++];
			while (left <= right&&sum >= s) {
				ans = min(ans, right - left);
				sum -= nums[left++];
			}
		}
		return ans == INT_MAX ? 0 : ans;
	}
};

本代码提交AC,用时13MS。

解法2,二分查找,O(nlgn)。我们先想想暴力方法,枚举每个left,从left开始枚举right,直到累加和第一次超过sum,更新最短长度。这样两层循环,时间复杂度是O(n^2)的。有没有办法把内层查找right的时间复杂度降低呢?

遇到子数组和的问题,马上要想到借助累加和数组。所以我们先求到原数组的累加和数组accuSum[n+1],其中accuSum[i]等于原数组中前i-1个数之和。我们利用accuSum来循环right,对于每个left,它要找一个right,使得left和right之间的和大于等于s,也就相当于在accuSum中找一个right,使得accuSum[right]>=accuSum[left]+s,等价于accuSum[right]-accuSum[left]>=s,即left到right的累加和大于等于s。因为原数组是正整数数组,所以accuSum是递增有序的,所以我们可以在accuSum中二分查找。即查找right的复杂度降为了O(lgn),所以总的复杂度就是O(nlgn)了。

完整代码如下:

class Solution {
private:
	int searchRight(vector<int>& accuSum, int l, int r, int target) {
		while (l <= r) {
			int m = l + (r - l) / 2;
			if (accuSum[m] == target)return m;
			else if (accuSum[m] > target)r = m - 1;
			else l = m + 1;
		}
		return l;
	}
public:
	int minSubArrayLen(int s, vector<int>& nums) {
		int n = nums.size(), ans = INT_MAX;
		vector<int> accuSum(n + 1, 0);
		for (int i = 1; i <= n; ++i)accuSum[i] = accuSum[i - 1] + nums[i - 1];
		for (int left = 0; left < n; ++left) {
			int right = searchRight(accuSum, left, accuSum.size() - 1, accuSum[left] + s);
			if (right == n + 1)break;
			ans = min(ans, right - left);
		}
		return ans == INT_MAX ? 0 : ans;
	}
};

本代码提交AC,用时16MS。

Leave a Reply

Your email address will not be published. Required fields are marked *