Subarray Sum closest

Java

//前缀和数组模版 - 找最接近 0 的
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
     */
		//[0]: sum , [1]:index    template 
		public int[] subarraySumClosest(int[] nums) {
			List<int[]> prefix = new ArrayList<>();
			prefix.add(new int[]{0, -1});
		
			int sum = 0;
			for (int i = 0; i < nums.length; i++) {
				sum += nums[i];
				prefix.add(new int[]{sum, i});
			}
				//prefix[j] - prefix[i] → sum of sub[i + 1, …. , j]
			Collections.sort(prefix, (a, b) -> (a[0] - b[0]));
			int min = Integer.MAX_VALUE;
			int[] res = new int[2];
			for (int i = 1; i < prefix.size(); i++) {
				if (prefix.get(i)[0] - prefix.get(i - 1)[0] <= min) {
					min = prefix.get(i)[0] - prefix.get(i - 1)[0];
					res = new int[]{prefix.get(i)[1], prefix.get(i - 1)[1]};
				}
			}
			Arrays.sort(res); //保证数组区间前小后大
			res[0]++; //因为 sum of sum 是不包括 i 在内的； 
			return res;
		}
}

Time Complexity : O(nlogn);
Space Complexity : O(n);