Example: array = {1, 2, 3, 4, 5, 6, 7, 8, 9}; k = 30 Output: 4 This is because the sub array [6, 7, 8, 9]
This problem can be solved with “two pointers with sliding window approach” solution.
Algorithm:
Step 1: Increase right pointer till the sum is greater than or equal to the key.
Step 2: Then increase the left pointer to right pointer till the sum is less than the key.
Step 3: Store the minimum length in a variable.
Solution in C++
#include<iostream> #include<vector> using namespace std; int min_sub_array_len(vector<int>& nums, int key) { int left = 0; int right = 0; int length = nums.size(); int sum = 0; int len = INT_MAX; cout<<"=================start debugging==============="<<endl; while (right < length) { sum += nums[right++]; cout<<"Step 1: sum = "<<sum<<" right = "<<right<<" left = "<<left<<endl; while (sum >= key) { len = min(len, right - left); sum -= nums[left++]; cout<<"Step 2: sum = "<<sum<<" right = "<<right<<" left = "<<left<< " len = min(len, right - left) = "<<min(len, right - left)<<endl; } } cout<<"=================end debugging==============="<<endl; return len == INT_MAX ? 0 : len; } int main() { vector<int> array = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int key = 30; int len = min_sub_array_len(array, key); cout<<"\n\nThe minimum length of continuous sub array is "<<len<<endl; return 0; }
Output:
================start debugging=============== Step 1: sum = 1 right = 1 left = 0 Step 1: sum = 3 right = 2 left = 0 Step 1: sum = 6 right = 3 left = 0 Step 1: sum = 10 right = 4 left = 0 Step 1: sum = 15 right = 5 left = 0 Step 1: sum = 21 right = 6 left = 0 Step 1: sum = 28 right = 7 left = 0 Step 1: sum = 36 right = 8 left = 0 Step 2: sum = 35 right = 8 left = 1 len = min(len, right - left) = 7 Step 2: sum = 33 right = 8 left = 2 len = min(len, right - left) = 6 Step 2: sum = 30 right = 8 left = 3 len = min(len, right - left) = 5 Step 2: sum = 26 right = 8 left = 4 len = min(len, right - left) = 4 Step 1: sum = 35 right = 9 left = 4 Step 2: sum = 30 right = 9 left = 5 len = min(len, right - left) = 4 Step 2: sum = 24 right = 9 left = 6 len = min(len, right - left) = 3 =================end debugging=============== The minimum length of continuous sub array is 4