Description

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

Solution

1. 用prefix sum的思路，遍历得到一个数组sum[n]， 用来记录0~n的sum
2. sort数组sum， 遍历求相邻sum之间diff的最小值
3. 因为要记录index，所以给sum数组的元素建立一个包含sum和index的一个新class

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
     */

       private class Sum implements Comparable<Sum> {
           public int index;
           public int sum;
           public Sum(int index, int sum) {
               this.index = index;
               this.sum = sum;
           }

           public int compareTo(Sum s) {
               return this.sum - s.sum;
           }
       }

    public int[] subarraySumClosest(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return new int[] {0, 0};
        }

        Sum[] sum = new Sum[nums.length + 1];
        sum[0] = new Sum(-1, 0);

        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = new Sum(i, sum[i].sum + nums[i]);
        }

        Arrays.sort(sum);

        int start = 0; 
        int end = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int diff = Math.abs(sum[i + 1].sum - sum[i].sum);
            if (diff < min) {
                min = diff;
                start = Math.min(sum[i].index, sum[i + 1].index) + 1;
                end = Math.max(sum[i].index, sum[i + 1].index);
            }
        }

        return new int[] {start, end};
    }
}