算法面試真題i詳解：最接近零的子數組和

給定一個整數數組，找到一個和最接近于零的子數組。傳回第一個和最右一個指數。你的代碼應該傳回滿足要求的子數組的起始位置和結束位置。

• 資料保證任意數的和都在[-2^31,2^31−1]範圍内

線上評測位址：

領扣題庫官網

樣例

輸入: 
[-3,1,1,-3,5] 
輸出: 
[0,2]
解釋: [0,2], [1,3], [1,1], [2,2], [0,4]           

算法：字首和優化+排序貪心

• 先對數組求一遍字首和，然後把字首和排序，令排完序的字首和是B數組
• 題目要求子數組的和最接近0，也就是B數組兩個值相減最接近0
• 既然B數組兩個值相減最接近0，也就是B數組兩個最接近的數
• 對B數組排序，最接近的數肯定是相鄰的
• 排完序後，我們隻要找相鄰元素做差就好了

B=sort(sums)for i in 1:n

res=B[i]-B[i-1]

ans=min(ans,res)

這樣隻需要一重枚舉。

複雜度分析

N是輸入的數組長度

時間複雜度

• 字首和預處理O(N)
• 排序O(NlogN)
• 相鄰元素做差O(N)
• 最終複雜度O(NlogN)

空間複雜度：開辟空間和輸入數組同階，O(N)

public class Solution {
    static class Node implements Comparator<Node> {
        public int value;
        public int idx;

        public Node() {

        }
        //value權值大小，arraysIdx在哪個數組裡，idx在該數組的哪個位置> >
        public Node(int value, int idx) {
            this.value = value;
            this.idx = idx;
        }

        public int compare(Node n1, Node n2) {
            if(n1.value < n2.value) {
                return 1;
            } else {
                return 0;
            }
        }
    }
    static Comparator<Node> cNode = new Comparator<Node>() {
        public int compare(Node o1, Node o2) {
            return o1.value - o2.value;
        }

    };
    public int[] subarraySumClosest(int[] nums) {

        // write your code here
        //字首和數組，并記錄下标位置
        ArrayList<Node> sums = new ArrayList<Node>();
        for(int i = 0; i < nums.length; i++) {
            if(i == 0) {
                sums.add(new Node(nums[i], 0));
            } else {
                sums.add(new Node(nums[i] + sums.get(i - 1).value, i));
            }
        }
        Collections.sort(sums, cNode);
        //維護最小的絕對值以及位置
        int mn = 2147483647;
        int ans1 = 0, ans2 = 1;
        for(int i = 0; i < sums.size(); i++) {
            if(mn >= Math.abs(sums.get(i).value)) {
                //[0,idx] 這段子數組的和
                mn = Math.abs(sums.get(i).value);
                ans1 = 0;
                ans2 = sums.get(i).idx;
            }
            if(i > 0) {
                // [lastidx+1,nowidx]這段子數組的和
                int lastidx = sums.get(i - 1).idx;
                int nowidx = sums.get(i).idx;
                int lastsum = sums.get(i - 1).value;
                int nowsum = sums.get(i).value;
                if(mn >= Math.abs(nowsum - lastsum)) {
                    mn = Math.abs(nowsum - lastsum);
                    ans1 = Math.min(lastidx, nowidx) + 1;
                    ans2 = Math.max(lastidx, nowidx);
                }
            }
        }
        int []ans = new int[2];
        ans[0] = ans1;
        ans[1] = ans2;
        return ans;
    }
}           

更多題解參考：

九章官網solution