[笔试题]找数组中最长和为0连续子序列

1、暴力求解法

很容易想到，用两个下标i，j来遍历数组，然后将i和j之间的元素求和，这样的方法比较简单，因为下标i和j都遍历了数组，所以时间复杂度有 $O（n^2）$ ，加上求和，所以总的时间复杂度是 $O(n^3)$ ，而空间存储只需要保留i和j还有一个最大长度的变量，所以空间复杂度为 $O（1）$ .

2、动态规划法

上面方法耗时主要在求和，如果可以将部分求和的结果先保存起来，则会省不少时间，可以考虑用一个数组a，a[i]存储从下标0到i的所有元素的和，这个求和时间复杂度为 $O（n）$ 。然后用两个下标遍历i，j。但是求i到j的和只需要a[j]-a[i]，这样时间复杂度只有 $O（n^2）$ ，空间复杂度为 $O（n）$ ，以空间换时间.

这里也可以用一个hashtable降低时间复杂度到 $O（n）$ ，空间复杂度为 $2*O（n）$ ，参考3.
- 看图片：若某一个前缀和为 0，说明该项之前（包含该项在内）的子数组之和为 0 ；两个前缀和如果相等，则说明两者相差的数据之和为 0；所以本文为了消除前缀和为0的单独考虑，就把sum[0]=0; i从0开始，sum[i+1]=sum[i]+num[i]。这样要是出现0就可以出现两个0.
- 将问题统一转化为求SUM数组两个相同数字最远距离

code：

 
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<assert.h>
#include<math.h>
using namespace std;
 
void MaxSubSumof0(vector<int>num,vector<int>&res)
{
	int maxlen = 0; int maxi, maxj;
	vector<int>sum(num.size() + 1, 0);
	for (int i = 0; i < num.size(); i++)
		sum[i + 1] = sum[i] + num[i];
	for (int i = 0; i < sum.size(); i++)
	{
		for (int j = sum.size()-1; j >= i; j--)
		{
			if (sum[i] == sum[j])
			{
				if (maxlen < j - i)
				{
					maxlen = j - i;
					maxi = i;
					maxj = j;
				}
				break;//这次循环是最大的，中间有重复的忽略
			}
		}
	}
	for (int i = maxi; i < maxj; i++)
		res.push_back(num[i]);
	int i = 0;
	for ( i = 0; i<res.size()-1; i++)
		cout << res[i] << " ";
	cout << res[i] << endl;
}
int main(){	 
	int n,i;
	cin >> n;
	vector<int>num(n, 0);
	vector<int>res;
	for ( i = 0; i<num.size(); i++)
		cin >> num[i];
	MaxSubSumof0(num, res);
	return 0;
}

test 用例:
[笔试题]找数组中最长和为0连续子序列

参考1
参考2
参考3

[笔试题]找数组中最长和为0连续子序列

相关推荐