Presum数组的建立 - Subarray Sum and c

遇到subarray sum的问题，需要建立presum数组。presum的数组建立如下。

1. 用hash table建立，简单

2. 如果需要对presum进行排序。同时还要记录presum值，与index的对应关系时，建立vector<Node> presum, 其中Node记录sum与index。

3. 不管怎么建立，always要初始化presum[0] = -1。表示index -1，对应sum为0，来对应从index 0开始的结果。同时，presum的区间，是(presum[small]+1, presum[large]), 有加1.

4. Subarray Sum:

sum为0，表示前后presum值应该相等，注意扩展到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数组进行排序，然后两两比较(presum[i], presum[i+1])。因为排序后相邻两数之间差最小。

这道题如果扩展到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;
    }
};