Subarray Sum Closest Show result

Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Have you met this question in a real interview? 

Yes

Example

Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4]

Challenge

O(nlogn) time

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 ArrayList<Integer> subarraySumClosest(int[] nums) {

        // write your code here

        ArrayList<Integer> res = new ArrayList<Integer>();

        res.add(0);

        res.add(0);

        ArrayList<Pair> record = new ArrayList<>();

        if(nums == null || nums.length <= 1) return res;

      //  map.add(0,0);

        int sum = 0;

        for(int i = 0; i < nums.length; i++){

            sum += nums[i];

            record.add(new Pair(sum, i));

        }

        int minError = Integer.MAX_VALUE;

        Collections.sort(record, new Comparator<Pair>(){

            public int compare(Pair l1, Pair l2){

                return l1.a - l2.a;

            }

        });

        for(int i = 1; i < record.size(); i++){

            

          

            int error = Math.abs(record.get(i).a - record.get(i-1).a);

            if(error >= minError) continue;

            minError = error;

            res.set(0, Math.min(record.get(i).b, record.get(i-1).b) + 1);

            res.set(1, Math.max(record.get(i).b, record.get(i-1).b));

        }

        return res;

    }

    

    public class Pair{

        int a;

        int b;

        public Pair(int a, int b){

            this.a = a;

            this.b = b;

        }

    }

}