http://www.lintcode.com/en/problem/subarray-sum-closest/#
思路1：Brute Force
枚举子数组，其中用一个Hash Map保存子数组的abs(sum)以及区间信息，最后返回abs(sum)最小的子数组区间。
Time complexity: O(n^2)
Space complexity: O(n^2)
此方法在LintCode上会超时。
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> ret;unordered_map<long long, pair<int, int> > mymap;long long min_dis = INT_MAX;for (int i = 0; i < nums.size(); ++i) {long long sum = 0;for (int j = i; j < nums.size(); ++j) {sum += nums[j];long long dis = abs(sum);if (dis < min_dis) {min_dis = dis;mymap[min_dis] = make_pair(i, j);}}}pair<int, int> &interval = mymap[min_dis];ret.push_back(interval.first);ret.push_back(interval.second);return ret;} };思路2：Prefix Sum + Sort
计算所有的前缀和并记录位置信息，然后按前缀和排序，依次计算相邻两个前缀和的差，找到差最小的两个区间，输出目标区间即可。
Time complexity: O(n log n)
Space complexity: O(n)
写的过程中我是自定义了前缀和数据结构并且重载了operator<，其实可以直接用C++的pair<int, int>容器。
struct PrefixSum {long long sum;int pos;PrefixSum(long long _sum = 0, int _pos = 0) : sum(_sum), pos(_pos) {}bool operator< (const PrefixSum &other) const {return (this->sum < other.sum || (this->sum == other.sum && this->pos < other.pos ));} };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> ret;if (nums.empty()) return ret;vector<PrefixSum> prefix_sum(nums.size());prefix_sum[0] = PrefixSum(nums[0], 0);for (int i = 1; i < nums.size(); ++i) {prefix_sum[i] = PrefixSum(prefix_sum[i-1].sum + nums[i], i);}sort(prefix_sum.begin(), prefix_sum.end());long long closest_val = INT_MAX;int start = 0, end = 0;for (int i = 1; i < prefix_sum.size(); ++i) {long long val = prefix_sum[i].sum - prefix_sum[i-1].sum;if (val < closest_val) {start = min(prefix_sum[i].pos, prefix_sum[i-1].pos) + 1;end = max(prefix_sum[i].pos, prefix_sum[i-1].pos);closest_val = val;}}ret.push_back(start); ret.push_back(end);return ret;} }; 思路3：Prefix Sum + BST / Tree Map
扫描一遍数组，过程中构造每一个位置的前缀和sum并维护一颗以前缀和为key的二叉搜索树(Tree Map)。对于每个sum，在BST中查找与其最接近的前缀和，这一步须要考察大于等于sum的最小值，以及小于sum的最大值，可以调用std::map的lower_bound()函数实现查找。
Time complexity: O(n log n)
Space complexity: O(n)
该方法不仅适用于查找最接近0的子数组，也可以推广到查找最接近k的子数组，查找的时候改为查找sum - k即可。
该方法出自: http://stackoverflow.com/questions/16388930/how-to-find-the-subarray-that-has-sum-closest-to-zero-or-a-certain-value-t-in-o
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> ret;int n = nums.size();if (n == 0) return ret;int start = 0, end = 0;map<long long, int> tree_map;tree_map[0] = -1;tree_map[LLONG_MIN] = -2; tree_map[LLONG_MAX] = n; // barrierslong long sum = 0, min_val = LLONG_MAX;for (int i = 0; i < n; ++i) {sum += nums[i];map<long long, int>::iterator it = tree_map.lower_bound(sum);// it->first >= sum, and with the minimal value in tree maplong long dis = it->first - sum;if (dis < min_val) {min_val = dis;start = it->second + 1;end = i;}it--; // it->first < sum, and with the maximal value in tree mapdis = sum - it->first;if (dis < min_val) {min_val = dis;start = it->second + 1;end = i;}tree_map[sum] = i;}ret.push_back(start); ret.push_back(end);return ret;} };