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

Example

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

Challenge

O(nlogn) time

Analysis:

s[i] = nums[0]+....nums[i], also record the index i into s[i]. Sort array s, and the minimum difference between two consecutive element, is the the subarray.

Solution:

1 class Element implements Comparable
       
        { 2     int val; 3     int index; 4     public Element(int v, int i){ 5         val = v; 6         index = i; 7     } 8  9     public int compareTo(Element other){10         return this.val - other.val;11     }12 13     public int getIndex(){14         return index;15     }16 17     public int getValue(){18         return val;19     }20 }21 22 public class Solution {23     /**24      * @param nums: A list of integers25      * @return: A list of integers includes the index of the first number26      *          and the index of the last number27      */28     public ArrayList
        
          subarraySumClosest(int[] nums) {29         ArrayList
         
           res = new ArrayList
          
           ();30         if (nums.length==0) return res;31 32         Element[] sums = new Element[nums.length+1];33         sums[0] = new Element(0,-1);34         int sum = 0;35         for (int i=0;i