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].
O(nlogn) time
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
vector<int> res;
vector<pair<int, int>> prefixSum;
prefixSum.push\_back\({0, -1}\);
int sum = 0;
for \(int i = 0; i < nums.size\(\); ++i\) {
sum += nums\[i\];
prefixSum.push\_back\({sum, i}\);
}
auto cmp = \[\]\(pair<int, int> a, pair<int, int> b\) {
return a.first < b.first;
};
sort\(prefixSum.begin\(\), prefixSum.end\(\), cmp\);
int diff = INT\_MAX, minDiffIdx = -1;
for \(int i = 0; i < prefixSum.size\(\) - 1; ++i\) {
if \(prefixSum\[i + 1\].first - prefixSum\[i\].first < diff\) {
minDiffIdx = i;
diff = prefixSum\[i + 1\].first - prefixSum\[i\].first;
}
}
if \(prefixSum\[minDiffIdx\].second
< prefixSum\[minDiffIdx + 1\].second\) {
res.push\_back\(prefixSum\[minDiffIdx\].second + 1\);
res.push\_back\(prefixSum\[minDiffIdx + 1\].second\);
} else {
res.push\_back\(prefixSum\[minDiffIdx + 1\].second + 1\);
res.push\_back\(prefixSum\[minDiffIdx\].second\);
}
return res;
}
};