九章算法 | Google 面试题：最接近零的子数组和

给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最右一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置。

• 数据保证任意数的和都在[-2^​31​​,2^​31​​−1]范围内

在线评测地址：LintCode 领扣

样例

输入: 
[-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;
    }
}

更多题解参考：九章算法