Minimum Size Subarray Sum Equals k

自己编的

Description:

Given an array nums and a target value k, find the minimum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example:

Note

Idea:

与Maximum Size Subarray Sum Equals k基本类似，却别就是每次得到sum都更行hash table。

Method 2: 是不是也可以用前一种方法做，不用hashmap。

Code:

Method 1:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        unordered_map<int, int> hash_tb;
        hash_tb[0]=-1;

        int min_len=INT_MAX;
        int sum=0;
        for(int i=0; i<nums.size(); ++i){
            sum += nums[i];

            if(hash_tb.find(sum-s)!=hash_tb.end()){
                min_len = min(min_len, i-hash_tb[sum-s]);
            }
            hash_tb[sum]=i;
        }
        return min_len==INT_MAX? 0: min_len;        
    }
};

Method 2: 改自Minimum Size Subarray Sum，不用extra space。

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

using namespace std;

int minSubArrayLen(int s, vector<int>& nums) {
    if(nums.size()==0)
        return 0;

    int sum=0;
    int min_len=INT_MAX;
    int j=0;
    for(int i=0; i<nums.size(); ++i){
        sum += nums[i];
        while(sum>s){
            sum -= nums[j];
            j++;
        }
        if(sum==s){
            min_len=min(min_len, i-j+1);
        }
    }

    return min_len;

}

int main(){
    vector<int> arr={1,2,3,4,10,16,5};
    cout<<minSubArrayLen(16, arr);
}