欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-01 13:05:26
...

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

  • 数据保证任意数的和都在[-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;
    }
}

更多题解参考:九章算法