原题网址：https://www.lintcode.com/problem/subarray-sum/description
描述
给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置
There is at least one subarray that it's sum equals to zero.
您在真实的面试中是否遇到过这个题？
样例
给出 [-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].
标签
哈希表
子数组
思路1：设置两根指针start与end，每次查找固定start，end向右移动，遍历数组，找到和为0的return出去。这种属于暴力破解，时间复杂度O（n^2），空间复杂度O（1）。【时间596ms】
AC代码：
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
vector<int> result;
int n=nums.size();
int sum;
int start=0,end=0;
for (;start<n;start++)
{
sum=nums[start];
end=start;
while(end<n-1&&sum!=0)//end<n-1防止end++后数组索引超出范围;
{
end++;
sum+=nums[end];
}
if (sum==0)
{
result.push_back(start);
result.push_back(end);
return result;
}
}
}
};
思路2：利用哈希表，创建一个map，记录从第一个元素开始到当前元素之和 与 当前元素下标 的对应关系，若有一段子数组和为0，那么一定有一个和对应两个下标，此时就找到了一段连续的和为0的子数组，时间复杂度O（n），空间复杂度O（n）。转自此处
AC代码：
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
vector<int> result;
int n=nums.size();
map<int,int> m;
m[0]=-1;//初始化哈希表，以防和为零的序列正好从第一个元素开始;
int sum=0;
for (int i=0;i<n;i++)
{
sum+=nums[i];
if (m.find(sum)!=m.end())
{
result.push_back(m[sum]+1);
result.push_back(i);
return result;
}
m.insert(pair<int,int>(sum,i));
}
}
};
如果不对map初始化m[0] = -1，则 if 程序块可以改成：
if (m.find(sum)!=m.end())
{
result.push_back(m[sum]+1);
result.push_back(i);
return result;
}
else if (m.find(sum)==m.end()&&sum==0)
{
result.push_back(0);
result.push_back(i);
return result;
}
else
{
m.insert(pair<int,int>(sum,i));
}
参考：
https://blog.csdn.net/github_34248245/article/details/50903849
https://www.aliyun.com/jiaocheng/374347.html
https://blog.csdn.net/weiyanjie100/article/details/79026862
https://blog.csdn.net/ljlstart/article/details/48393675