遇到subarray sum的问题，需要建立presum数组。presum的数组建立如下。
用hash table建立，简单
如果需要对presum进行排序。同时还要记录presum值，与index的对应关系时，建立vector<Node> presum, 其中Node记录sum与index。
不管怎么建立，always要初始化presum[0] = -1。表示index -1，对应sum为0，来对应从index 0开始的结果。同时，presum的区间，是(presum[small]+1, presum[large]), 有加1.
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;
}
- 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;
}
};
