image.png
解法一：
暴力搜索，遍历两个坐标的可能性，O(n^2);
解法二：
类似于暴力搜索，但是！！记录的是累加和，当两个位置的累加和一样的时候，说明这一段为0；由于寻找两个数是否一样，还是需要o(n^2)的时间。
解法三: 哈希表！！！
用hash存储，每次加入的时候，检查下是否存在一样的。
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
*/
vector<int> subarraySum(vector<int> &nums) {
// write your code here
unordered_map<int, int> umap;
int cur_sum = 0;
vector<int> result;
for(int i = 0; i < nums.size(); i++){
cur_sum += nums[i];
if(cur_sum == 0){
result.push_back(0);
result.push_back(i);
break;
}
if(umap.find(cur_sum) == umap.end()){
umap[cur_sum] = i;
}
else{
result.push_back(umap.find(cur_sum)->second + 1);
result.push_back(i);
break;
}
}
return result;
}
};
