Zero Sum Subarray · 數據結構與算法/leetcode/lintcode題解

# Zero Sum Subarray ### Source - lintcode: [(138) Subarray Sum](http://www.lintcode.com/en/problem/subarray-sum/) - GeeksforGeeks: [Find if there is a subarray with 0 sum - GeeksforGeeks](http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/) ~~~ Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number. Example Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3]. Note There is at least one subarray that it's sum equals to zero. ~~~ ### 題解1 - 兩重 for 循環題目中僅要求返回一個子串(連續)中和為0的索引，而不必返回所有可能滿足題意的解。最簡單的想法是遍歷所有子串，判斷其和是否為0，使用兩重循環即可搞定，最壞情況下時間復雜度為 O(n2)O(n^2)O(n2), 這種方法顯然是極其低效的，極有可能會出現 [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。"). 下面就不浪費篇幅貼代碼了。 ### 題解2 - 比較子串和([TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")) 兩重 for 循環顯然是我們不希望看到的解法，那么我們再來分析下題意，題目中的對象是分析子串和，那么我們先從常見的對數組求和出發，f(i)=∑0inums[i]f(i) = \sum _{0} ^{i} nums[i]f(i)=∑0inums[i] 表示從數組下標 0 開始至下標 i 的和。子串和為0，也就意味著存在不同的 i1i_1i1 和 i2i_2i2 使得 f(i1)?f(i2)=0f(i_1) - f(i_2) = 0f(i1)?f(i2)=0, 等價于 f(i1)=f(i2)f(i_1) = f(i_2)f(i1)=f(i2). 思路很快就明晰了，使用一 vector 保存數組中從 0 開始到索引`i`的和，在將值 push 進 vector 之前先檢查 vector 中是否已經存在，若存在則將相應索引加入最終結果并返回。 ### C++ ~~~ 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){ vector<int> result; int curr_sum = 0; vector<int> sum_i; for (int i = 0; i != nums.size(); ++i) { curr_sum += nums[i]; if (0 == curr_sum) { result.push_back(0); result.push_back(i); return result; } vector<int>::iterator iter = find(sum_i.begin(), sum_i.end(), curr_sum); if (iter != sum_i.end()) { result.push_back(iter - sum_i.begin() + 1); result.push_back(i); return result; } sum_i.push_back(curr_sum); } return result; } }; ~~~ ### 源碼分析使用`curr_sum`保存到索引`i`處的累加和，`sum_i`保存不同索引處的和。執行`sum_i.push_back`之前先檢查`curr_sum`是否為0，再檢查`curr_sum`是否已經存在于`sum_i`中。是不是覺得這種方法會比題解1好？錯！時間復雜度是一樣一樣的！根本原因在于`find`操作的時間復雜度為線性。與這種方法類似的有哈希表實現，哈希表的查找在理想情況下可認為是 O(1)O(1)O(1). ### 復雜度分析最壞情況下 O(n2)O(n^2)O(n2), 實測和題解1中的方法運行時間幾乎一致。 ### 題解3 - 哈希表終于到了祭出萬能方法時候了，題解2可以認為是哈希表的雛形，而哈希表利用空間換時間的思路爭取到了寶貴的時間資源 :) ### C++ ~~~ 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){ vector<int> result; // curr_sum for the first item, index for the second item 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) != hash.end()) { result.push_back(hash[curr_sum]); result.push_back(i); return result; } else { hash[curr_sum] = i + 1; } } return result; } }; ~~~ ### 源碼分析為了將`curr_sum == 0`的情況也考慮在內，初始化哈希表后即賦予 `<0, 0>`. 給 `hash`賦值時使用`i + 1`, `push_back`時則不必再加1. 由于 C++ 中的`map`采用紅黑樹實現，故其并非真正的「哈希表」，C++ 11中引入的`unordered_map`用作哈希表效率更高，實測可由1300ms 降至1000ms. ### 復雜度分析遍歷求和時間復雜度為 O(n)O(n)O(n), 哈希表檢查鍵值時間復雜度為 O(logL)O(\log L)O(logL), 其中 LLL 為哈希表長度。如果采用`unordered_map`實現，最壞情況下查找的時間復雜度為線性，最好為常數級別。 ### 題解4 - 排序除了使用哈希表，我們還可使用排序的方法找到兩個子串和相等的情況。這種方法的時間復雜度主要集中在排序方法的實現。由于除了記錄子串和之外還需記錄索引，故引入`pair`記錄索引，最后排序時先按照`sum`值來排序，然后再按照索引值排序。如果需要自定義排序規則可參考[sort_pair_second](#). ### C++ ~~~ 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){ vector<int> result; if (nums.empty()) { return result; } const int num_size = nums.size(); vector<pair<int, int> > sum_index(num_size + 1); for (int i = 0; i != num_size; ++i) { sum_index[i + 1].first = sum_index[i].first + nums[i]; sum_index[i + 1].second = i + 1; } sort(sum_index.begin(), sum_index.end()); for (int i = 1; i < num_size + 1; ++i) { if (sum_index[i].first == sum_index[i - 1].first) { result.push_back(sum_index[i - 1].second); result.push_back(sum_index[i].second - 1); return result; } } return result; } }; ~~~ ### 源碼分析沒啥好分析的，注意好邊界條件即可。這里采用了鏈表中常用的「dummy」節點方法，`pair`排序后即為我們需要的排序結果。這種排序的方法需要先求得所有子串和然后再排序，最后還需要遍歷排序后的數組，效率自然是比不上哈希表。但是在某些情況下這種方法有一定優勢。 ### 復雜度分析遍歷求子串和，時間復雜度為 O(n)O(n)O(n), 空間復雜度 O(n)O(n)O(n). 排序時間復雜度近似 O(nlogn)O(n \log n)O(nlogn), 遍歷一次最壞情況下時間復雜度為 O(n)O(n)O(n). 總的時間復雜度可近似為 O(nlogn)O(n \log n)O(nlogn). 空間復雜度 O(n)O(n)O(n). ### 擴展這道題的要求是找到一個即可，但是要找出所有滿足要求的解呢？Stackoverflow 上有這道延伸題的討論[stackoverflow](#). 另一道擴展題來自 Google 的面試題 - [Find subarray with given sum - GeeksforGeeks](http://www.geeksforgeeks.org/find-subarray-with-given-sum/). ### Reference - stackoverflow > . [algorithm - Zero sum SubArray - Stack Overflow](http://stackoverflow.com/questions/5534063/zero-sum-subarray)[ ?](# "Jump back to footnote [stackoverflow] in the text.") - sort_pair_second > . [c++ - How do I sort a vector of pairs based on the second element of the pair? - Stack Overflow](http://stackoverflow.com/questions/279854/how-do-i-sort-a-vector-of-pairs-based-on-the-second-element-of-the-pair)[ ?](# "Jump back to footnote [sort_pair_second] in the text.")