algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 };