【Leetcode】209. Minimum Size Subarray Sum(求子区间)
程序员文章站
2024-02-24 22:17:46
...
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.
Example:
Input:s = 7, nums = [2,3,1,2,4,3]
Output: 2 Explanation: the subarray[4,3]
has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
题目大意:
题目中给出一个目标,和一个数组,求出长度最少的区间满足和>=s。
解题思路:
从第一个位置开始遍历,当找到满足要求时将左标签l向右移动。保存最小距离,再将右标签r向右移动。
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
// O(n) l and r
int n = nums.size();
int ans = INT_MAX;
int l = 0, r = 0;
int sum = 0;
while(r<n){
sum += nums[r];
while(sum>=s){
ans = min(ans, r+1-l);
sum -= nums[l++];
}
r++;
}
return (ans==INT_MAX)?0:ans;
}
};
上一篇: 回文、循环、Python
下一篇: 寒假集训个人赛 D