遇到subarray sum的問題，需要建立presum數(shù)組。presum的數(shù)組建立如下。

1. 用hash table建立，簡單

2. 如果需要對presum進行排序。同時還要記錄presum值，與index的對應(yīng)關(guān)系時，建立vector<Node> presum, 其中Node記錄sum與index。

3. 不管怎么建立，always要初始化presum[0] = -1。表示index -1，對應(yīng)sum為0，來對應(yīng)從index 0開始的結(jié)果。同時，presum的區(qū)間，是(presum[small]+1, presum[large]), 有加1.

4. Subarray Sum:

sum為0，表示前后presum值應(yīng)該相等，注意擴展到sum為any target的情況。

vector<int> subarraySum(vector<int> nums){
        // write your code here
        vector<int> ret;
        if(nums.empty()) return ret;
        unordered_map<int, int> mp;
        mp[0] = -1;
        int sum = 0;
        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
            if(mp.count(sum)){
                ret.push_back(mp[sum]+1);
                ret.push_back(i);
                break;
            }
            mp[sum] = i;
        }
        return ret;
    }

2. Subarray Sum Cloest
   http://www.lintcode.com/en/problem/subarray-sum-closest/#

這道題的思路是對presum數(shù)組進行排序，然后兩兩比較(presum[i], presum[i+1])。因為排序后相鄰兩數(shù)之間差最小。

這道題如果擴展到cloest to a target，則比較難。需要用Treeset來找 lower bound。擴展閱讀如下：
https://rafal.io/posts/subsequence-closest-to-t.html

class Solution {
public:
    /**
     * @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
     */
    struct Node{
        int value, idx; 
        Node(int v, int i) : value(v), idx(i){}
    }; 
    
    static bool comp(const Node &n1, const Node &n2){
        return n1.value < n2.value;
    }
    vector<int> subarraySumClosest(vector<int> nums){
        // write your code here
        if(nums.empty()) return vector<int>();
        vector<int> ret(2, 0);
        int len = nums.size();
        vector<Node> presum;
        presum.push_back(Node(0, -1));
        int sum = 0;
        for(int i=0; i<len; i++){
            sum += nums[i];
            presum.push_back(Node(sum, i));
        }
        sort(presum.begin(), presum.end(), comp);
        int min_diff = INT_MAX;
        for(int i=0; i<presum.size()-1; i++){
            int diff = abs(presum[i+1].value - presum[i].value);
            if(diff < min_diff){
                min_diff = diff;
                ret[0] = min(presum[i].idx, presum[i+1].idx)+1;
                ret[1] = max(presum[i].idx, presum[i+1].idx);
            }
        }
        return ret;
    }
};