描述

給定一個整數(shù)數(shù)組，找到一個和最接近于零的子數(shù)組。返回第一個和最有一個指數(shù)。你的代碼應(yīng)該返回滿足要求的子數(shù)組的起始位置和結(jié)束位置

樣例

給出[-3, 1, 1, -3, 5]，返回[0, 2]，[1, 3]， [1, 1]， [2, 2] 或者 [0, 4]

思路

求完和之后排個序，值接近的兩個子數(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;

        // 只有一個數(shù)時起始下標(biāo)為0；
        if(len == 1) {
            res[0] = res[1] = 0;
            return res;
        }

        Pair[] sums = new Pair[len+1];
        // 前0個數(shù)之和
        // 這里是為只有第一個元素的子數(shù)組準(zhǔn)備的 
        int prev = 0;
        // 在sums起始位置多添加一組數(shù)sums[0]，方便計算
        sums[0] = new Pair(0, 0);
        // 給sum[]數(shù)組賦值
        // 無論是nums[]數(shù)組還是sums數(shù)組都是從下標(biāo)0開始
        for (int i = 1; i <= len; i++) {
            // sums.sum表示前i個數(shù)之和，從nums開始數(shù)到第i-1個數(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時更新ans
            if (ans > sums[i].sum - sums[i-1].sum) {
                // 尋找ans的最小值，即最接近于0的子數(shù)組和
                ans = sums[i].sum - sums[i-1].sum;
                // temp將得到的index排序，保證起始點的index不大于結(jié)束點的index
                int[] temp = new int[]{sums[i].index - 1, sums[i - 1].index - 1};
                // 調(diào)用默認(rèn)的ASCII碼排序
                Arrays.sort(temp);
                /* 因為sum的index是原數(shù)組中index為(0, i-1)的和，
                 * 存入temp的時候，index要減1才是真正的index；假如i > j ，
                 * 那么sum(0, i) - sum(0, j)表示的是(j + 1, i)這一段的和，所以要給小的那個加1
                 */
                res[0] = temp[0] + 1;
                res[1] = temp[1];
            }
        }
        
        return res;
    }
}

問：

為什么需要一個 (0,0) 的初始 Pair?

答：

我們首先需要回顧一下，在 subarray 這節(jié)課里，我們講過一個重要的知識點，叫做 Prefix Sum
比如對于數(shù)組 [1,2,3,4]，他的 Prefix Sum 是 [1,3,6,10]
分別表示 前1個數(shù)之和，前2個數(shù)之和，前3個數(shù)之和，前4個數(shù)之和
這個時候如果你想要知道 子數(shù)組 從下標(biāo) 1 到下標(biāo) 2 的這一段的和(2+3)，就用前 3個數(shù)之和 減去 前1個數(shù)之和 = PrefixSum[2] - PrefixSum[0] = 6 - 1 = 5
你可以看到這里的 前 x 個數(shù)，和具體對應(yīng)的下標(biāo)之間，存在 +-1 的問題
第 x 個數(shù)的下標(biāo)是 x - 1，反之 下標(biāo) x 是第 x + 1 個數(shù)
那么問題來了，如果要計算 下標(biāo)從 0~2 這一段呢？也就是第1個數(shù)到第3個數(shù)，因為那樣會訪問到 PrefixSum[-1]
所以我們把 PrefixSum 整體往后面移動一位，把第0位空出來表示前0個數(shù)之和，也就是0. => [0,1,3,6,10]
那么此時就用 PrefixSum[3] - PrefixSum[0] ，這樣計算就更方便了。
此時，PrefixSum[i] 代表 前i個數(shù)之和，也就是 下標(biāo)區(qū)間在 0 ~ i-1 這一段的和
那么回過頭來看看，為什么我們需要一個 (0,0) 的 pair 呢？
因為 這個 0,0 代表的就是前0個數(shù)之和為0
一個 n 個數(shù)的數(shù)組， 變成了 prefix Sum 數(shù)組之后，會多一個數(shù)出來

關(guān)于自定義Arrays.sort:

    Arrays.sort(objects, new Comparator<Object>() {  
            public int compare(Object object1, Object object2) {  
  
                    return object1.num - object2.num;  
            
        });  

比如這樣，主要是重寫compare方法，返回一個你需要的值來進(jìn)行排序,這個返回值就是排序 的依據(jù),比如要按object的num進(jìn)行升序排序，就可以根據(jù)object1.num - object2.num來排序,如果返回的是object2.num - object1.num的話實際效果就是降序