https://leetcode.com/problems/minimum-size-subarray-sum/
X. Two pointers
X. Binary Search
Time complexity: .
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).
X. Two pointers
int minSubArrayLen(int s, vector<int>& nums)
{
int n = nums.size();
int ans = INT_MAX;
int left = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
while (sum >= s) {
ans = min(ans, i + 1 - left);
sum -= nums[left++];
}
}
return (ans != INT_MAX) ? ans : 0;
}
X. Binary Search
int minSubArrayLen(int s, vector<int>& nums)
{
int n = nums.size();
if (n == 0)
return 0;
int ans = INT_MAX;
vector<int> sums(n + 1, 0); //size = n+1 for easier calculations
//sums[0]=0 : Meaning that it is the sum of first 0 elements
//sums[1]=A[0] : Sum of first 1 elements
//ans so on...
for (int i = 1; i <= n; i++)
sums[i] = sums[i - 1] + nums[i - 1];
for (int i = 1; i <= n; i++) {
int to_find = s + sums[i - 1];
auto bound = lower_bound(sums.begin(), sums.end(), to_find);
if (bound != sums.end()) {
ans = min(ans, static_cast<int>(bound - (sums.begin() + i - 1)));
}
}
return (ans != INT_MAX) ? ans : 0;
}
Time complexity: .
int minSubArrayLen(int s, vector<int>& nums)
{
int n = nums.size();
if (n == 0)
return 0;
int ans = INT_MAX;
vector<int> sums(n);
sums[0] = nums[0];
for (int i = 1; i < n; i++)
sums[i] = sums[i - 1] + nums[i];
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int sum = sums[j] - sums[i] + nums[i];
if (sum >= s) {
ans = min(ans, (j - i + 1));
break; //Found the smallest subarray with sum>=s starting with index i, hence move to next index
}
}
}
return (ans != INT_MAX) ? ans : 0;
}
Time complexity: .
int minSubArrayLen(int s, vector<int>& nums)
{
int n = nums.size();
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += nums[k];
}
if (sum >= s) {
ans = min(ans, (j - i + 1));
break; //Found the smallest subarray with sum>=s starting with index i, hence move to next index
}
}
}
return (ans != INT_MAX) ? ans : 0;
}
