Subarray Sum to K

Given an nonnegative integer array, find a subarray where the sum of numbers is k.

Your code should return the index of the first number and the index of the last number.

Example

Given [1, 4, 20, 3, 10, 5], sum k = 33, return [2, 4].

Solution

核心约束条件变成 f(i1) - f(i2) = k

vector<int> subarraySum(vector<int> nums, int k){
    vector<int> result;
    // curr_sum for the first item, index for the second item
    // unordered_map<int, int> hash;
    map<int, int> hash;
    hash[0] = 0;

    int curr_sum = 0;
    for (int i = 0; i != nums.size(); ++i) {
        curr_sum += nums[i];
        if (hash.find(curr_sum - k) != hash.end()) {
            result.push_back(hash[curr_sum - k]);
            result.push_back(i);
            return result;
        } else {
            hash[curr_sum] = i + 1;
        }
    }

    return result;
}

与上一题的变化之处有两个地方，第一个是判断是否存在哈希表中时需要使用hash.find(curr_sum - k), 最终返回结果使用result.push_back(hash[curr_sum - k]);而不是result.push_back(hash[curr_sum]);

利用单调函数特性的方法

f(i)为单调不减函数，题中要寻找 f(i2) - f(i1) = k 则必有 f(i2) >= k，类似于两个指针的方法来进行遍历

vector<int> subarraySum2(vector<int> nums, int k){
    vector<int> result;

    int left_index = 0;
    int curr_sum = 0;
    for (int i = 0; i != nums.size(); ++i) {
        curr_sum += nums[i];
        if (curr_sum == k) {
            result.push_back(left_index);
            result.push_back(i);
            return result;
        }

        while (curr_sum > k) {
            curr_sum -= nums[left_index];
            ++left_index;
        }
    }

    return result;
}

使用for循环累加curr_sum, 在curr_sum > k时再使用while递减curr_sum, 同时递增左边索引left_index.