# Subarray Sum K ### Source - GeeksforGeeks: [Find subarray with given sum - GeeksforGeeks](http://www.geeksforgeeks.org/find-subarray-with-given-sum/) ~~~ 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 | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/integer_array/zero_sum_subarray.html) 的升級版，這道題求子串和為 K 的索引。首先我們可以考慮使用時間復雜度相對較低的哈希表解決。前一道題的核心約束條件為 f(i1)?f(i2)=0f(i_1) - f(i_2) = 0f(i1)?f(i2)=0，這道題則變為 f(i1)?f(i2)=kf(i_1) - f(i_2) = kf(i1)?f(i2)=k ### 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; } ~~~ ### 源碼分析 與 Zero Sum Subarray 題的變化之處有兩個地方，第一個是判斷是否存在哈希表中時需要使用`hash.find(curr_sum - k)`, 最終返回結果使用`result.push_back(hash[curr_sum - k]);`而不是`result.push_back(hash[curr_sum]);` ### 復雜度分析 略，見 [Zero Sum Subarray | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/integer_array/zero_sum_subarray.html) ### 題解2 - 利用單調函數特性 不知道細心的你是否發現這道題的隱含條件——**nonnegative integer array**, 這也就意味著子串和函數 f(i)f(i)f(i) 為「單調不減」函數。單調函數在數學中可是重點研究的對象，那么如何將這種單調性引入本題中呢？不妨設 i2>i1i_2 > i_1i2>i1, 題中的解等價于尋找 f(i2)?f(i1)=kf(i_2) - f(i_1) = kf(i2)?f(i1)=k, 則必有 f(i2)≥kf(i_2) \geq kf(i2)≥k. 我們首先來舉個實際例子幫助分析，以整數數組 {1, 4, 20, 3, 10, 5} 為例，要求子串和為33的索引值。首先我們可以構建如下表所示的子串和 f(i)f(i)f(i). | f(i)f(i)f(i) | 1 | 5 | 25 | 28 | 38 | |-----|-----|-----|-----|-----|-----| | iii | 0 | 1 | 2 | 3 | 4 | 要使部分子串和為33，則要求的第二個索引值必大于等于4，如果索引值再繼續往后遍歷，則所得的子串和必大于等于38，進而可以推斷出索引0一定不是解。那現在怎么辦咧？當然是把它扔掉啊！第一個索引值往后遞推，直至小于33時又往后遞推第二個索引值，于是乎這種技巧又可以認為是「兩根指針」。 ### 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; } ~~~ ### 源碼分析 使用`for`循環, 在`curr_sum > k`時使用`while`遞減`curr_sum`, 同時遞增左邊索引`left_index`, 最后累加`curr_sum`。如果順序不對就會出現 bug, 原因在于判斷子串和是否滿足條件時在遞增之后(謝謝 @glbrtchen 匯報 bug)。 ### 復雜度分析 看似有兩重循環，由于僅遍歷一次數組，且索引最多挪動和數組等長的次數。故最終時間復雜度近似為 O(2n)O(2n)O(2n), 空間復雜度為 O(1)O(1)O(1). ### Reference - [Find subarray with given sum - GeeksforGeeks](http://www.geeksforgeeks.org/find-subarray-with-given-sum/)