Lintcode：Subarray Sum Closest/ subarray sum closest to k

这个解法比较复杂，用到了treemap。
是通用与找closest to target k 的解法。简单解法参考subarray sum。排序即可。

import java.util.Map.Entry;
public class Solution {
    public ArrayList<Integer> subarraySumClosest(int[] nums) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	if (nums == null || nums.length == 0) {
    		return res;
    	}
    	TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();
    	long sum = 0;
    	long minDiff = (long)Integer.MAX_VALUE + 1;
    	res.add(0);
    	res.add(0);
    	for (int i = 0; i < nums.length; i++) {
    		sum += nums[i];
    		Entry floorEntry = map.floorEntry(sum);
    		Entry ceilingEntry = map.ceilingEntry(sum);
    		int curDiff = 0;
    		if (floorEntry != null || ceilingEntry != null) {
	    		if (floorEntry == null || (ceilingEntry != null && Math.abs((long)floorEntry.getKey() - sum) > Math.abs((long)ceilingEntry.getKey() - sum))) {
	    			if (Math.abs((long)ceilingEntry.getKey() - sum) < minDiff) {
	    				res.set(0, (int)ceilingEntry.getValue() + 1);
	    				res.set(1, i);
	    			}
	    		} else {
	    			if (Math.abs((long)floorEntry.getKey() - sum) < minDiff) {
	    				res.set(0, (int)floorEntry.getValue() + 1);
	    				res.set(1, i);
	    				minDiff = Math.abs((long)floorEntry.getKey() - sum);
	    			}
	    		}
    		}
    		map.put(sum, i);
    	}	    	
    	return res;
    }
}