最接近零的子数组和

问题描述

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

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

样例

样例1

输入: 
[-3,1,1,-3,5] 
输出: 
[0,2]
解释: [0,2], [1,3], [1,1], [2,2], [0,4]

挑战

O(nlogn)的时间复杂度

问题分析

解法一

先不考虑 时间复杂度 nlogn的要求 很明显就是枚举所有子数组。也就是枚举所有的start end 求和。

代码

public int[] subarraySumClosest(int[] nums) {
       // write your code here
        int sum = 0;
        for(int index = 0;index < nums.length;index ++){
            sum += nums[index];
            nums[index] = sum;
        }
        int[] ans = new int[2];
        int result = Integer.MAX_VALUE;
        for (int i = 0; i<nums.length; i++){
            for(int j = i; j < nums.length;j++){
                int temp = nums[j] - (i > 0? nums[i - 1] : 0);
                if(Math.abs(temp) < Math.abs(result)){
                    ans[0] = i;
                    ans[1] = j;
                    result = temp;
                }
            }
        }
        return ans;
    }

结果 超时

分析 有什么方式可以减少数组的访问次数

最接近零的子数组和也就是和要相近 相减才可能为0 所以对和进行排序 相邻的和相减就行了

代码

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
     */
    static class Pair{
        public int sum;
        public int index;

        Pair(int sum, int index){
            this.sum = sum;
            this.index = index;
        }
    }
    public int[] subarraySumClosest(int[] nums) {
       // write your code here
        int sum = 0;
        Pair[] pairs = new Pair[nums.length + 1];
        pairs[0] = new Pair(0, 0);
        for(int index = 0;index < nums.length;index ++){
            sum += nums[index];
            pairs[index + 1] = new Pair(sum, index + 1);
        }
        quickSort(pairs, 0, pairs.length-1);

        int[] ans = new int[2];
        int result = Integer.MAX_VALUE;
        for (int i = 1; i < pairs.length; i++){
            int temp = pairs[i].sum - pairs[i - 1].sum;
            if(Math.abs(temp) < Math.abs(result)){
                ans[0] = Math.min(pairs[i].index, pairs[i - 1].index);
                ans[1] = Math.max(pairs[i].index, pairs[i - 1].index) - 1;
                result = temp;
            }
        }
        return ans;
    }
    
    private static void quickSort(Pair[] num, int start, int end){
        if(start >= end){
            return;
        }
        int ii = start;
        int jj = end;
        while (ii < jj){
            while (ii < jj && num[ii].sum <= num[jj].sum){
                ii ++;
            }
            if(ii < jj && num[ii].sum > num[jj].sum){
                Pair temp = num[ii];
                num[ii] = num[jj];
                num[jj] = temp;
            }
            while (ii < jj && num[ii].sum <= num[jj].sum){
                jj --;
            }
            if(ii < jj && num[ii].sum > num[jj].sum){
                Pair temp = num[ii];
                num[ii] = num[jj];
                num[jj] = temp;
            }
        }

        quickSort(num, start, ii-1);
        quickSort(num, ii+1, end);
    }
}

这条题目的重点在于减少遍历的次数