139.Subarray Sum Closest

1.Description(Medium)

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].

2.Code

这里同样可以记录下位置i的sum，存入一个数组或者链表中，按照sum的值sort，再寻找相邻两个sum差值绝对值最小的那个，也就得到了subarray sum closest to 0。

用一个helper class 来记录index和sum。prefix sum 排序,但是排序的时候要重新写comparator.

class Helper{
    public int sum;
    public int index;
    public Helper(int sum,int index){
        this.sum=sum;
        this.index=index;
    }
}
public class Solution_139 {
     /**
     * @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 int[] subarraySumClosest(int[] nums) {
        if(nums==null || nums.length==0){
            return null;
        }
        int[] result=new int[2];
        int sum=0;
        Helper[] list=new Helper[nums.length];
        for(int i=0;i<nums.length;i++){
            sum=sum+nums[i];
            Helper helper=new Helper(sum,i);
            list[i]=helper;
        }
        Arrays.sort(list,new Comparator<Helper>(){
            public int compare(Helper a,Helper b){
                return a.sum-b.sum;
            }
        });
        int ans=Integer.MAX_VALUE;
        for(int i=1;i<list.length;i++){
            if(list[i].sum-list[i-1].sum<ans){
                ans=list[i].sum-list[i-1].sum;
                //can not make sure which index is smaller
                int[] temp=new int[]{list[i].index,list[i-1].index};
                Arrays.sort(temp);
                result[0]=temp[0]+1;
                result[1]=temp[1];
            }
        }
        return result;        
    }
}