很多问题可以转化成最基本的subarray sum问题 二维矩阵处理 可以表示从左上角（0，0)到(i,j)的面积

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.

为什么closest 就要sort然后一前一后比较差值？本质上还是subarray 问题

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
     */
    class Pair {
        int sum;
        int index;
        public Pair(int s, int i) {
            sum = s;
            index = i;
        }
    }
    public int[] subarraySumClosest(int[] nums) {
        int[] res = new int[2];
        if (nums == null || nums.length == 0) {
            return res;
        } 

        int len = nums.length;
        if(len == 1) {
            res[0] = res[1] = 0;
            return res;
        }
        Pair[] sums = new Pair[len+1];
        sums[0] = new Pair(0, 0);
        //prefix sum
        for (int i = 1; i <= len; i++) {
            sums[i] = new Pair(sums[i-1].sum + nums[i-1], i);
        }
        //personalized sort according to the sum value 
        Arrays.sort(sums, new Comparator<Pair>() {
           public int compare(Pair a, Pair b) {
               return a.sum - b.sum;
           } 
        });
        //sweep and compare the adjacent element's value's subtract 
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= len; i++) {
            if (ans > sums[i].sum - sums[i-1].sum) {
                ans = sums[i].sum - sums[i-1].sum;
                int[] temp = new int[]{sums[i].index - 1, sums[i - 1].index - 1};
                Arrays.sort(temp);
                res[0] = temp[0] + 1;
                res[1] = temp[1];
            }
        }
        return res;
    }
}

2D Matrix

Submatrix Sum

O(N2) * O(N) = O(N3)

枚举可能出现的行数对(row1,row2) 计算每一列对应范围内的值