minimum-size-subarray-sum.cpp (1590B)
1 class Solution { 2 public: 3 int minSubArrayLen(int target, vector<int>& nums) { 4 // find the shortest contiguous subarray (redundant) whose sum is at least target 5 // first thought: 6 // can we use prefix sums? 7 // idea: 8 // compute inclusive prefix sums for each element 9 // O(n^2) tc bc we check each pairing 10 // hashmaps are out 11 // sliding window 12 // start from left side 13 // if current sum < target move right ptr 14 // if current sum >= target move left ptr 15 16 int leftPtr = 0; 17 int rightPtr = 0; 18 int sum = nums[0]; 19 int shortest = nums.size()+2; 20 while(rightPtr < nums.size()) { 21 if(sum >= target) { 22 if((rightPtr - leftPtr) + 1 < shortest) { 23 shortest = (rightPtr - leftPtr) + 1; 24 } 25 if(leftPtr < rightPtr) { 26 sum -= nums[leftPtr]; 27 leftPtr += 1; 28 } else { 29 rightPtr += 1; 30 if(rightPtr < nums.size()) { 31 sum += nums[rightPtr]; 32 } 33 } 34 } else { 35 rightPtr += 1; 36 if(rightPtr < nums.size()) { 37 sum += nums[rightPtr]; 38 } 39 } 40 } 41 if(shortest == nums.size() + 2) { 42 return 0; 43 } 44 return shortest; 45 } 46 };