138. 子数组之和 map存储加规律
给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。 假定一定存在这样的字数组。 样例 给出 [-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].
map存储加规律
遍历数组，求第一个元素到达当前元素的累加和，如果累加和出现0，或者累加和有重复出现，那么就找到和为0的子数组了。
- 累加和为0： 这个好理解，如果累加和是0的话，那么从第一个数到当前元素就是要找的子数组。比如：
num | -3 | 2 | 1 | 2 | 3 |
|---|---|---|---|---|---|
sum | -3 | -1 | 0 | 2 | 5 |
index | 0 | 1 | 2 | 3 | 4 |
这里累加到1的时候出现了0，那么说明从第一个数到1这个数的累加和是0，很好理解。
- 累加和有重复。 如有重复，说明两个重复累加和之间的那些数应该和是0.比如：
num | 1 | -2 | -3 | 3 | 2 |
|---|---|---|---|---|---|
sum | 1 | -1 | -4 | -1 | 1 |
index | 0 | 1 | 2 | 3 | 4 |
这里index=0和index=4的两个累加和相同了，说明这两个累计和之间的所有数的和是0，其实也很好理解，只是没想到可以这么做。 代码写起来就比较简单了，为了代码统一，先把0存起来，因为一下子要存两个数，所以这里用了map。还可以很简单的利用map的find函数。
vector<int> subarraySum(vector<int> nums){
// write your code here
int sum = 0;
vector<int> ret;
unordered_map<int, int> map;
map[0] = -1; //这个是把0先加进去了，
for(int i=0; i<nums.size();i++)
{
sum += nums[i];
if(map.find(sum) != map.end())
{ cout<<map.find(sum)->first<<endl;
ret.push_back(map[sum] +1);
ret.push_back(i);
return ret;
}
map[sum] = i;
}
return ret;
} 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017.12.06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
