#139 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.

Have you met this question in a real interview?  Yes Example

Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2]or [0, 4].

Challenge 

O(nlogn) time

题目思路：

这题同样用遍历两遍的思路可以解，但是代价是O(n^2)。题目要求用O(nlogn)解，那么又想到了sort的思路了。首先，求出一个对应的presum array，这个presum的每个值presum[i]代表了所有<= i的元素的和。然后用一个map记录好每个presum的值对应的index，再把presum从小到大排序得到sorted presum。题目要求求closest sum，可以转换思考为presum中最接近的两个数，那么最有可能成为closest sum的，则是sorted presum中相邻的两个元素。找到这两个元素，再根据这两个元素的值找到map中所对应的index即可。

Mycode（AC = 3299ms）：

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){ // write your code here map<int, vector<int>> helper; vector<int> ans(2, 0); vector<int> presum(nums.size() + 1, 0); if (nums.size() < 2) return ans; // get presum of each i: the sum of all // elements <= i for (int i = 1; i <= nums.size(); i++) { presum[i] = presum[i - 1] + nums[i - 1]; } // use a map to store the presum value vs. // index in the original presum for (int i = 0; i <= nums.size(); i++) { helper[presum[i]].push_back(i); } int diff = INT_MAX; // sort presum sort(presum.begin(), presum.end()); // the min diff only exists between // each neighbored element for(int i = 1; i <= nums.size(); i++) { int tmp = abs(presum[i] - presum[i - 1]); if (tmp < diff) { diff = tmp; ans[0] = i; ans[1] = i - 1; } } // get the corresponding index in the // original presum array vector<int> idx1 = helper[presum[ans[0]]]; vector<int> idx2 = helper[presum[ans[1]]]; for (int i = 0; i < idx1.size(); i++) { for (int j = 0; j < idx2.size(); j++) { if (idx1[i] > idx2[j]) { ans[0] = idx2[j]; ans[1] = idx1[i] - 1; break; } else if (idx1[i] < idx2[j]) { ans[1] = idx2[j] - 1; ans[0] = idx1[i]; break; } } } return ans; } };