Dare2Solve
The goal is to find the minimal length of a subarray whose sum is greater than or equal to the target. We can utilize the sliding window technique to efficiently solve this problem. By maintaining a window that expands and contracts, we can keep track of the sum and update the minimal length dynamically.
Initialize Variables:
min_length
to float('inf')
to store the minimal length of the subarray found.sum
to 0 to keep track of the sum of the current window.left
to 0 to represent the starting index of the current window.Expand the Window:
for
loop to iterate through the array with right
representing the end index of the current window.nums[right]
to sum
to include the current element in the window.Shrink the Window:
while
loop to check if sum
is greater than or equal to the target.min_length
with the smaller value between min_length
and the current window size (right - left + 1
).nums[left]
from sum
and increment left
to shrink the window from the left side.Return Result:
min_length
was updated from float('inf')
.min_length
. Otherwise, return 0, indicating no valid subarray was found.O(n), where n
is the length of the array. Each element is processed at most twice, once by the right
pointer and once by the left
pointer.
O(1), as the solution only uses a constant amount of extra space for the pointers and variables.
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int minLen = INT_MAX;
int right = 0;
int sum = 0;
int left = 0;
while (right < nums.size()) {
sum += nums[right];
while (sum >= target) {
minLen = min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return minLen == INT_MAX ? 0 : minLen;
}
};
from typing import List
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
min_length = float('inf')
right = 0
sum = 0
left = 0
while right < len(nums):
sum += nums[right]
while sum >= target:
min_length = min(min_length, right - left + 1)
sum -= nums[left]
left += 1
right += 1
return 0 if min_length == float('inf') else min_length
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minLength = Integer.MAX_VALUE;
int right = 0;
int sum = 0;
int left = 0;
while (right < nums.length) {
sum += nums[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}
var minSubArrayLen = function (target, nums) {
let min = Infinity
let right = 0
let sum = 0
let left = 0
while (right < nums.length) {
sum += nums[right]
while (sum >= target) {
min = Math.min(min, (right - left + 1))
sum -= nums[left]
console.log("min", min)
left++
}
right++
}
return min == Infinity ? 0 : min
};