# Subarray Sum K

## Question

### Problem Statement

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].

## 题解1 - 哈希表

Zero Sum Subarray 的升级版，这道题求子串和为 K 的索引。首先我们可以考虑使用时间复杂度相对较低的哈希表解决。前一道题的核心约束条件为 $f(i_1) - f(i_2) = 0$，这道题则变为 $f(i_1) - f(i_2) = k$, 那么相应的 index 则为 $[i_1 + 1, i_2]$.

### C++

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Solution {
public:
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
*          and the index of the last number
*/
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;
}
};

int main(int argc, char *argv[])
{
int int_array1[] = {1, 4, 20, 3, 10, 5};
int int_array2[] = {1, 4, 0, 0, 3, 10, 5};
vector<int> vec_array1;
vector<int> vec_array2;
for (int i = 0; i != sizeof(int_array1) / sizeof(int); ++i) {
vec_array1.push_back(int_array1[i]);
}
for (int i = 0; i != sizeof(int_array2) / sizeof(int); ++i) {
vec_array2.push_back(int_array2[i]);
}

Solution solution;
vector<int> result1 = solution.subarraySum(vec_array1, 33);
vector<int> result2 = solution.subarraySum(vec_array2, 7);

cout << "result1 = [" << result1[0] << " ," << result1[1] << "]" << endl;
cout << "result2 = [" << result2[0] << " ," << result2[1] << "]" << endl;

return 0;
}


## 题解2 - 利用单调函数特性

$f(i)$ 1 5 25 28 38
$i$ 0 1 2 3 4

### C++

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Solution {
public:
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
*          and the index of the last number
*/
vector<int> subarraySum2(vector<int> &nums, int k){
vector<int> result;

int left_index = 0, curr_sum = 0;
for (int i = 0; i != nums.size(); ++i) {
while (curr_sum > k) {
curr_sum -= nums[left_index];
++left_index;
}

if (curr_sum == k) {
result.push_back(left_index);
result.push_back(i - 1);
return result;
}
curr_sum += nums[i];
}
return result;
}
};

int main(int argc, char *argv[])
{
int int_array1[] = {1, 4, 20, 3, 10, 5};
int int_array2[] = {1, 4, 0, 0, 3, 10, 5};
vector<int> vec_array1;
vector<int> vec_array2;
for (int i = 0; i != sizeof(int_array1) / sizeof(int); ++i) {
vec_array1.push_back(int_array1[i]);
}
for (int i = 0; i != sizeof(int_array2) / sizeof(int); ++i) {
vec_array2.push_back(int_array2[i]);
}

Solution solution;
vector<int> result1 = solution.subarraySum2(vec_array1, 33);
vector<int> result2 = solution.subarraySum2(vec_array2, 7);

cout << "result1 = [" << result1[0] << " ," << result1[1] << "]" << endl;
cout << "result2 = [" << result2[0] << " ," << result2[1] << "]" << endl;

return 0;
}