Subarray Sum Closest解题报告

Description:

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

Link:

[http://www.lintcode.com/en/problem/subarray-sum-closest/]

解题思路：

这道题求的是和最接近于0的子序列，暴力做法应该是N*N的时间复杂度，但是不能AC，所以在这里需要观察，所有子序列和的集合 = {0~n的子序列和，0~n的子序列和 - 0~m的子序列和}，这里m<n。
所以由此我们可以知道，当(0_{n的子序列和)与(0}m的子序列和)值非常接近的时候，则（m+1~n）即为所要求的最接近0的子序列。

解题方法：

当我们求到所有从0开始的子序列和，对其进行排序再遍历，我们可以得到每两个最接近的从0开始的子序列和。至于排序后没有相邻的子序列和，则不进行考虑，因为最小的差值不会从不相邻的两个子序列和里面产生。在求所有0~m的子序列和的过程中应该记录下m对应的值（可以自定义数据结构或者用pair）。

Tips:

当用sort对含有pair的vector进行排序的时候，会优先针对pair::first进行排序，所以这道题可以不需要自己写排序函数。

Time Complexity：

sort函数的时间复杂度为：O(nlogn)

完整代码：

vector<int> subarraySumClosest(vector<int> nums) { if(nums.size() == 0) return {}; vector<pair<int, int> > node; node.push_back({0, 0}); int sum = 0; for(int i = 0; i < nums.size(); i++) { sum += nums[i]; if(sum == 0) return {0, i}; node.push_back({sum, i+1}); } std::sort(node.begin(), node.end()); int min = 2147483647; vector<int> result(2, 0); for(int i = 1; i < node.size(); i++) { int temp; temp = abs(node[i].first - node[i-1].first); if(temp < min) { min = temp; if(node[i].second < node[i-1].second) { result[0] = node[i].second; result[1] = node[i-1].second - 1; } else { result[0] = node[i-1].second; result[1] = node[i].second - 1; } } } return result; }