Subarray Sum Closest

LintCode LeetCode Array

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

这道题考点仍然是prefix Sum, 看来求subarray的问题跟这个方法脱不了干系。
连续数组的和其实就是前缀和之间的差，而要求和最接近于零，也就是说，两个前缀和要最接近，那么直接前缀和排序，相邻两项比较。

这里可以新建一个Pair类来记录prefixSum里面每个元素的sum和index.
第一步需要构建这个前缀和数组，注意index = 0处有一个前0个元素的和即sum = 0 的元素，所以前缀和数组的个数比nums多一个。

排序前缀和，然后比较后一个和前一个的差值，找到最小差值的一对。这就是我们要找的两个前缀和。但是注意这里的index不是我们要返回的原数组中的对应索引。

比如我们发现prefixSum[i] - prefixSum[i - 1]为最小前缀和差，那么我们先拿到这两个前缀和对应的index: prefixSum[i].index, prefixSum[i - 1].index,两者排序后为indexes[0], indexes1，我们就能知道在未排序时的prefixSum里面这两个前缀和的index了。

又注意到sum[i ~ j] = prefixSum[j + 1] - prefixSum[i],而这里的j+1 = indexes1, i = indexes[0];所以我们知道所求的子数列的起始位置是indexes[0], 终止位置是indexes1 - 1.