描述
給定一個(gè)整數(shù)數(shù)組稚虎，找到一個(gè)和最接近于零的子數(shù)組白嘁。返回第一個(gè)和最有一個(gè)指數(shù)但惶。你的代碼應(yīng)該返回滿足要求的子數(shù)組的起始位置和結(jié)束位置
樣例
給出[-3, 1, 1, -3, 5]枷遂，返回[0, 2]澈灼，[1, 3]竞川， [1, 1]， [2, 2] 或者 [0, 4]
思路
求完和之后排個(gè)序叁熔，值接近的兩個(gè)子數(shù)組和就相鄰了
代碼
class Pair {
int sum;
int index;
public Pair(int s, int i) {
sum = s;
index = i;
}
}
public class Solution {
/**
* @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
*/
public int[] subarraySumClosest(int[] nums) {
int[] res = new int[2];
if (nums == null || nums.length == 0) {
return res;
}
int len = nums.length;
// 只有一個(gè)數(shù)時(shí)起始下標(biāo)為0委乌；
if(len == 1) {
res[0] = res[1] = 0;
return res;
}
Pair[] sums = new Pair[len+1];
// 前0個(gè)數(shù)之和
// 這里是為只有第一個(gè)元素的子數(shù)組準(zhǔn)備的
int prev = 0;
// 在sums起始位置多添加一組數(shù)sums[0]，方便計(jì)算
sums[0] = new Pair(0, 0);
// 給sum[]數(shù)組賦值
// 無(wú)論是nums[]數(shù)組還是sums數(shù)組都是從下標(biāo)0開(kāi)始
for (int i = 1; i <= len; i++) {
// sums.sum表示前i個(gè)數(shù)之和荣回，從nums開(kāi)始數(shù)到第i-1個(gè)數(shù)
sums[i] = new Pair(prev + nums[i-1], i);
// prev后移一位
prev = sums[i].sum;
}
// 自定義排序遭贸，sums是需要排序的數(shù)組，new Comparator<Pair>(){}是自定義的排序方式心软，按照sums.sum大小排序
Arrays.sort(sums, new Comparator<Pair>() {
public int compare(Pair a, Pair b) {
return a.sum - b.sum;
}
});
int ans = Integer.MAX_VALUE;
for (int i = 1; i <= len; i++) {
// 排序后sums[i].sum - sums[i-1].sum一定是正值壕吹，滿足if時(shí)更新ans
if (ans > sums[i].sum - sums[i-1].sum) {
// 尋找ans的最小值，即最接近于0的子數(shù)組和
ans = sums[i].sum - sums[i-1].sum;
// temp將得到的index排序删铃，保證起始點(diǎn)的index不大于結(jié)束點(diǎn)的index
int[] temp = new int[]{sums[i].index - 1, sums[i - 1].index - 1};
// 調(diào)用默認(rèn)的ASCII碼排序
Arrays.sort(temp);
/* 因?yàn)閟um的index是原數(shù)組中index為(0, i-1)的和耳贬，
* 存入temp的時(shí)候，index要減1才是真正的index猎唁；假如i > j 咒劲，
* 那么sum(0, i) - sum(0, j)表示的是(j + 1, i)這一段的和，所以要給小的那個(gè)加1
*/
res[0] = temp[0] + 1;
res[1] = temp[1];
}
}
return res;
}
}
問(wèn)：
為什么需要一個(gè) (0,0) 的初始 Pair?
答：
我們首先需要回顧一下，在 subarray 這節(jié)課里腐魂，我們講過(guò)一個(gè)重要的知識(shí)點(diǎn)慕的，叫做 Prefix Sum
比如對(duì)于數(shù)組 [1,2,3,4]，他的 Prefix Sum 是 [1,3,6,10]
分別表示 前1個(gè)數(shù)之和挤渔，前2個(gè)數(shù)之和，前3個(gè)數(shù)之和风题，前4個(gè)數(shù)之和
這個(gè)時(shí)候如果你想要知道 子數(shù)組 從下標(biāo) 1 到下標(biāo) 2 的這一段的和(2+3)判导，就用前 3個(gè)數(shù)之和 減去 前1個(gè)數(shù)之和 = PrefixSum[2] - PrefixSum[0] = 6 - 1 = 5
你可以看到這里的 前 x 個(gè)數(shù)，和具體對(duì)應(yīng)的下標(biāo)之間沛硅，存在 +-1 的問(wèn)題
第 x 個(gè)數(shù)的下標(biāo)是 x - 1眼刃，反之 下標(biāo) x 是第 x + 1 個(gè)數(shù)
那么問(wèn)題來(lái)了，如果要計(jì)算 下標(biāo)從 0~2 這一段呢摇肌？也就是第1個(gè)數(shù)到第3個(gè)數(shù)擂红，因?yàn)槟菢訒?huì)訪問(wèn)到 PrefixSum[-1]
所以我們把 PrefixSum 整體往后面移動(dòng)一位，把第0位空出來(lái)表示前0個(gè)數(shù)之和围小，也就是0. => [0,1,3,6,10]
那么此時(shí)就用 PrefixSum[3] - PrefixSum[0] 昵骤，這樣計(jì)算就更方便了。
此時(shí)肯适，PrefixSum[i] 代表 前i個(gè)數(shù)之和变秦，也就是 下標(biāo)區(qū)間在 0 ~ i-1 這一段的和
那么回過(guò)頭來(lái)看看，為什么我們需要一個(gè) (0,0) 的 pair 呢框舔？
因?yàn)?這個(gè) 0,0 代表的就是前0個(gè)數(shù)之和為0
一個(gè) n 個(gè)數(shù)的數(shù)組蹦玫， 變成了 prefix Sum 數(shù)組之后，會(huì)多一個(gè)數(shù)出來(lái)
關(guān)于自定義Arrays.sort:
Arrays.sort(objects, new Comparator<Object>() {
public int compare(Object object1, Object object2) {
return object1.num - object2.num;
});
比如這樣刘绣，主要是重寫(xiě)compare方法樱溉，返回一個(gè)你需要的值來(lái)進(jìn)行排序,這個(gè)返回值就是排序 的依據(jù),比如要按object的num進(jìn)行升序排序，就可以根據(jù)object1.num - object2.num來(lái)排序,如果返回的是object2.num - object1.num的話實(shí)際效果就是降序
