Given an array of n positive integers and a positive integer s, find the minimal length of a contiguoussubarray 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).
Solution 1: Two Pointers (Sliding Window)
Maintain a sliding window [l, r) such that sum(nums[l:r)) >= s, then move l to l + 1, and move r accordingly to make the window valid.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int l = 0; int r = 0; int t = 0; int ans = INT_MAX; while (l < nums.size()) { while (t < s && r < nums.size()) t += nums[r++]; if (t < s) break; ans = min(ans, r - l); t -= nums[l++]; } return ans == INT_MAX ? 0 : ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment