Minimum Size Subarray Sum Solutions in C++

// Source : https://leetcode.com/problems/minimum-size-subarray-sum/
// Author : Hao Chen
// Date   : 2015-06-09




class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int min = nums.size();
        int begin=0, end=0;
        int sum = 0;
        bool has = false;
        
        for (int i=0; i<nums.size(); i++, end++){
            
            sum += nums[i];
            
            while (sum >= s && begin <= end) {
                //the 1 is minial length, just return
                if (begin == end) return 1;
                
                if (end-begin+1 < min) {
                    min = end - begin + 1;
                    has = true;
                }
                //move the begin
                sum -= nums[begin++];
            }
 
        }
        
        return has ? min : 0; 
    }
};

/// https://leetcode.com/problems/minimum-size-subarray-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-13

#include <iostream>
#include <cassert>
#include <vector>

using namespace std;


// Sum Prefix
// Time Complexity: O(n^2)
// Space Complexity: O(n)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {

        assert(s > 0);

        vector<int> sums(nums.size() + 1, 0);
        for(int i = 1 ; i <= nums.size() ; i ++)
            sums[i] = sums[i-1] + nums[i-1];

        int res = nums.size() + 1;
        for(int l = 0 ; l < nums.size() ; l ++)
            for(int r = l ; r < nums.size() ; r ++)
                if(sums[r+1] - sums[l] >= s)
                    res = min(res, r - l + 1);

        return res == nums.size() + 1 ? 0 : res;
    }
};


int main() {

    vector<int> nums1 = {2, 3, 1, 2, 4, 3};
    int s1 = 7;
    cout << Solution().minSubArrayLen(s1, vec1) << endl;

    return 0;
}

/// https://leetcode.com/problems/minimum-size-subarray-sum/description/
/// Author : liuyubobobo
/// Time   : 2019-03-03

#include <iostream>
#include <cassert>
#include <vector>

using namespace std;


// Brute Force + Greedy
// Time Complexity: O(n^2)
// Space Complexity: O(1)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {

        assert(s > 0);

        int res = nums.size() + 1;
        for(int l = 0 ; l < nums.size() ; l ++) {
            int sum = 0;
            for (int r = l; r < nums.size(); r++){
                sum += nums[r];
                if(sum >= s){
                    res = min(res, r - l + 1);
                    break;
                }
            }
        }

        return res == nums.size() + 1 ? 0 : res;
    }
};


int main() {

    vector<int> nums1 = {2, 3, 1, 2, 4, 3};
    int s1 = 7;
    cout << Solution().minSubArrayLen(s1, vec1) << endl;

    return 0;
}

/// https://leetcode.com/problems/minimum-size-subarray-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-13

#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>

using namespace std;


// Sum Prefix + Binary Search
// Time Complexity: O(nlogn)
// Space Complexity: O(n)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {

        assert(s > 0);

        vector<int> sums(nums.size() + 1, 0);
        for(int i = 1 ; i <= nums.size() ; i ++)
            sums[i] = sums[i-1] + nums[i-1];

        int res = nums.size() + 1;
        for(int l = 0; l < (int)nums.size(); l ++){
            auto r_bound = lower_bound(sums.begin(), sums.end(), sums[l] + s);
            if(r_bound != sums.end()){
                int r = r_bound - sums.begin();
                res = min(res, r - l);
            }
        }

        return res == nums.size() + 1 ? 0 : res;
    }
};

int main() {

    vector<int> nums1 = {2, 3, 1, 2, 4, 3};
    int s1 = 7;
    cout << Solution().minSubArrayLen(s1, nums1) << endl;
    // 2

    // ---

    vector<int> nums2 = {};
    int s2 = 100;
    cout << Solution().minSubArrayLen(s2, nums2) << endl;

    return 0;
}

/// https://leetcode.com/problems/minimum-size-subarray-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-13

#include <iostream>
#include <cassert>
#include <vector>

using namespace std;


// Sliding Window
// Time Complexity: O(n)
// Space Complexity: O(1)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {

        assert(s > 0);

        int l = 0 , r = -1; // sliding window: nums[l...r]
        int sum = 0;
        int res = nums.size() + 1;

        while(l < nums.size()){

            if(r + 1 < nums.size() && sum < s)
                sum += nums[++r];
            else
                sum -= nums[l++];

            if(sum >= s)
                res = min(res, r - l + 1);
        }

        return res == nums.size() + 1 ? 0 : res;
    }
};


int main() {

    vector<int> nums1 = {2, 3, 1, 2, 4, 3};
    int s1 = 7;
    cout << Solution().minSubArrayLen(s1, nums1) << endl;

    return 0;
}

/// https://leetcode.com/problems/minimum-size-subarray-sum/description/
/// Author : liuyubobobo
/// Time   : 2017-11-13

#include <iostream>
#include <cassert>
#include <vector>

using namespace std;


// Sliding Window
// Another Implementation
// Time Complexity: O(n)
// Space Complexity: O(1)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {

        assert(s > 0);

        int l = 0 , r = -1; // sliding window: nums[l...r]
        int sum = 0;
        int res = nums.size() + 1;

        while(r + 1 < nums.size()){

            while(r + 1 < nums.size() && sum < s)
                sum += nums[++r];

            if(sum >= s)
                res = min(res, r - l + 1);

            while(l < nums.size() && sum >= s){
                sum -= nums[l++];
                if(sum >= s)
                    res = min(res, r - l + 1);
            }
        }

        return res == nums.size() + 1 ? 0 : res;
    }
};


int main() {

    vector<int> nums1 = {2, 3, 1, 2, 4, 3};
    int s1 = 7;
    cout << Solution().minSubArrayLen(s1, nums1) << endl;

    return 0;
}