Skip to main content

[M] Minimum Size Subarray Sum

Đề bài

Cho một mảng số nguyên nums và một số nguyên target, hãy tìm độ dài của dãy con liên tiếp nhỏ nhất sao cho tổng các phần tử trong dãy con đó lớn hơn hoặc bằng target. Nếu không có dãy con nào thỏa mãn, trả về 0.

Ví dụ 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2

Ví dụ 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Constraints

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

Phân tích

Như mình có đề cập ở bài viết về kỹ thuật two pointers ta có thể sử dụng kỹ thuật này để giải bài toán này.

Pseudocode

Function minSubArrayLen(target, nums) {
left = 0
right = 0
sum = 0
minLen = Infinity
while right < nums.length {
sum += nums[right]
while sum >= target {
minLen = min(minLen, right - left + 1)
sum -= nums[left]
left++
}
right++
}
return minLen == Infinity ? 0 : minLen
}

}

Solution

class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
int left = 0, right = 0;
int sum = 0;
while (right < n) {
sum += nums[right];
while (sum >= target) {
ans = min(ans, right - left + 1);
sum -= nums[left];
left++;
}
right++;
}
return ans == INT_MAX ? 0 : ans;
}
}