preface
Here is the previous swipe card records, you can have a look, if you have any different views and views or feel what is wrong, welcome to leave a message in the comment area! 🙏 🙏 🙏
[LeetCode0303 topic area and retrieval – array immutable] | punch brush
[LeetCode1200. Minimum absolute difference] | punch brush
[LeetCode0304 topic 2 d area and retrieval – matrix immutable] | punch brush
[LeetCode11 topic containers of most water] | punch brush
[LeetCode0338 topic bit count] | punch brush
Topic describes
Given an array of n positive integers and a positive integer target.
Find the smallest contiguous subarray [numsl, numSL +1,…, numsr-1, numsr] that satisfies the sum and ≥ target, and return its length. If no subarray exists, return 0.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3] output: 2 description: the subarray [4,3] is the smallest subarray in this condition.Copy the code
Example 2:
Input: target = 4, nums = [1,4,4] Output: 1Copy the code
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1] output: 0Copy the code
Tip:
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
Advanced:
If you have implemented an O(n) time solution, try designing an O(n log(n)) time solution.
Their thinking
Given an array of n positive integers nums and a positive integer s, find the smallest contiguous subarray whose length is equal to and >= s.
Let’s set minLen as the sum of the subarrays. MinLen is set to maximum for comparison purposes because we want to minimize the length.
The sum of subarrays is the sum of the elements between left and right of the subarray.
Right moves to the right of nums, calculating the sum between left and right as it moves.
If sum is greater than s, then we’re satisfied with the sum and >= s, and then we don’t have to move right anymore, because we’re already satisfied with the length, and then we’re not going to be able to move right anymore.
Having satisfied the condition and >= s, we now need to satisfy the second condition of minimum length. If the first condition is satisfied, we move left to the right, and each time we compare the length of the current and last subarrays that satisfy the condition, minLen, keeping the smallest one, and so on.
If minLen is still the default maximum, there is no subarray that meets the condition, return 0, otherwise return minLen that meets the condition.
The problem solving code
var minSubArrayLen = function(s, nums) {
let minLe = Number.MAX_SAFE_INTEGER;
let left = 0, right = 0, sum = 0;
while (right < nums.length) {
sum += nums[right];
while(sum >= s) {
minLe = Math.min(minLe, right-left+1);
sum -= nums[left];
left++
}
right++;
}
return minLe == Number.MAX_SAFE_INTEGER ? 0 : minLe;
}
Copy the code
conclusion
Do not be afraid to write bad, dare to write is already very good, the process of writing is the process of review, it is easier to deepen their understanding.
Come on! HXDM!!!!!! 💪 💪 💪
This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign