# Subarray Sum Closest ### Source - lintcode: [(139) Subarray Sum Closest](http://www.lintcode.com/en/problem/subarray-sum-closest/) ~~~ Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number. Example Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4] Challenge O(nlogn) time ~~~ ### 題解 題 [Zero Sum Subarray | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/integer_array/zero_sum_subarray.html) 的變形題，由于要求的子串和不一定，故哈希表的方法不再適用，使用解法4 - 排序即可在 O(nlogn)O(n \log n)O(nlogn) 內解決。具體步驟如下： 1. 首先遍歷一次數組求得子串和。 1. 對子串和排序。 1. 逐個比較相鄰兩項差值的絕對值，返回差值絕對值最小的兩項。 ### 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> subarraySumClosest(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()); int min_diff = INT_MAX; int closest_index = 1; for (int i = 1; i < num_size + 1; ++i) { int sum_diff = abs(sum_index[i].first - sum_index[i - 1].first); if (min_diff > sum_diff) { min_diff = sum_diff; closest_index = i; } } int left_index = min(sum_index[closest_index - 1].second,\ sum_index[closest_index].second); int right_index = -1 + max(sum_index[closest_index - 1].second,\ sum_index[closest_index].second); result.push_back(left_index); result.push_back(right_index); return result; } }; ~~~ ### 源碼分析 為避免對單個子串和是否為最小情形的單獨考慮，我們可以采取類似鏈表 dummy 節點的方法規避，簡化代碼實現。故初始化`sum_index`時需要`num_size + 1`個。這里為避免 vector 反復擴充空間降低運行效率，使用`resize`一步到位。`sum_index`即最后結果中`left_index`和`right_index`等邊界可以結合簡單例子分析確定。 ### 復雜度分析 1. 遍歷一次求得子串和時間復雜度為 O(n)O(n)O(n), 空間復雜度為 O(n+1)O(n+1)O(n+1). 1. 對子串和排序，平均時間復雜度為 O(nlogn)O(n \log n)O(nlogn). 1. 遍歷排序后的子串和數組，時間復雜度為 O(n)O(n)O(n). 總的時間復雜度為 O(nlogn)O(n \log n)O(nlogn), 空間復雜度為 O(n)O(n)O(n). ### 擴展 - [algorithm - How to find the subarray that has sum closest to zero or a certain value t in O(nlogn) - Stack Overflow](http://stackoverflow.com/questions/16388930/how-to-find-the-subarray-that-has-sum-closest-to-zero-or-a-certain-value-t-in-o)