139.md

LintCode 139 Subarray Sum Closest

139. Subarray Sum Closest
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

idea

思路：当有sum=0的时候。则这是最近的，可以直接return
如果没有的话，就需要将所有的sum排序，然后循环两者差值、找到最小的diff、在这之前要用map记录sum和下标的对应关系

方法二：利用TreeMap 进行查询，如果之前出现过，那么必定为0。否则，找最近的一个数，大的或小的，然后求他们他们之间的差值，即为最小的subarray的sum值

方法一：不使用 pair，不使用 TreeMap，只使用 HashMap + Array + Sort 的方法. 用 HashMap 记录之前的位置，用 Array 来打擂台找最小差距
时间复杂度为O(nlogn), 空间复杂度为O(n)

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 int[] subarraySumClosest(int[] nums) {
        // write your code here
        int[] results = new int[2];
        
        // edge case
        if (nums == null || nums.length == 0) {
            return new int[]{};
        }
        if (nums.length == 1) {
            return new int[]{0,0};
        }
        
        // general
        Map<Integer, Integer> map = new HashMap<>();
        int[] prefixSum = new int[nums.length + 1];
        int sum = 0;
        map.put(0, -1);
        prefixSum[0] = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum)) {
                results[0] = map.get(sum) + 1;
                results[1] = i;
                return results;
            }
            map.put(sum, i);
            prefixSum[i + 1] = sum;
        }
        
        Arrays.sort(prefixSum);
        
        int minDiff = Integer.MAX_VALUE;
        int left = 0, right = 0;
        
        for (int i = 0; i < prefixSum.length - 1; i++) {
            if (minDiff > Math.abs(prefixSum[i] - prefixSum[i + 1])) {
                minDiff = Math.abs(prefixSum[i] - prefixSum[i + 1]);
                left = prefixSum[i];
                right = prefixSum[i + 1];
            }
        }
        if (map.get(left) < map.get(right)) {
            results[0] = map.get(left) + 1;
            results[1] = map.get(right);
        } else {
            results[0] = map.get(right) + 1;
            results[1] = map.get(left);
        }
        return results;
    }
}