Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
47 lines (47 sloc) 1.42 KB
/*
* @lc app=leetcode.cn id=209 lang=cpp
*
* [209] 长度最小的子数组
*
* https://leetcode-cn.com/problems/minimum-size-subarray-sum/description/
*
* algorithms
* Medium (36.91%)
* Total Accepted: 7.7K
* Total Submissions: 20.6K
* Testcase Example: '7\n[2,3,1,2,4,3]'
*
* 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
*
* 示例: 
*
* 输入: s = 7, nums = [2,3,1,2,4,3]
* 输出: 2
* 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
*
*
* 进阶:
*
* 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
*
*/
//分治法
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int res = INT_MAX, n = nums.size();
vector<int> sums(n + 1, 0);
for (int i = 1; i < n + 1; ++i) sums[i] = sums[i - 1] + nums[i - 1];
for (int i = 0; i < n; ++i) {
int left = i + 1, right = n, t = sums[i] + s;
while (left <= right) {
int mid = left + (right - left) / 2;
if (sums[mid] < t) left = mid + 1;
else right = mid - 1;
}
if (left == n + 1) break;
res = min(res, left - i);
}
return res == INT_MAX ? 0 : res;
}
};
You can’t perform that action at this time.