子序列求和
子序列求和
提问于 2013-02-14 08:12:20
给定一个整数数组，例如[1, 2, -3, 1]，查找是否存在求和为0的子序列并返回它(例如[1, 2, -3]或[2, -3, 1])。
检查每个子序列都是O(n^2)，这太低效了。有什么改进的想法吗？
回答 3
Stack Overflow用户
回答已采纳
发布于 2013-02-14 09:15:11
创建一个新的数组，每个元素等于前一个元素的和加上那个元素。
输入：
1 4 -3 -4 6 -7 8 -5变成：
1 5 2 -2 4 -3 5 0
^ ^然后在结果数组中查找匹配的元素。
由于这些位置表示函数中总体变化为零的位置，因此您会发现，如果它们的位置是i和k，则子序列(i+1，k)是零和子序列。(在本例中为2:6)。
此外，表中的任何零都表示子序列(0，k)是零和子序列。对于查找，哈希表或其他快速冲突定位器使此O(N)执行。
Stack Overflow用户
发布于 2014-10-16 05:05:09
下面是@Fabricio建议的解决方案的java实现
public static int countAllSubSequenceForZeroSum(int[] array) {
int count = 0;
Map<Integer, Integer> encounteredSum = new HashMap<>();
int prev = array[0];
if(prev == 0) {
count++;
System.out.println("Found at index: "+0);
}
for (int i = 1; i < array.length; i++) {
prev += array[i];
if(encounteredSum.containsKey(prev)) {
System.out.println("Found at index: "+i+ " start index: "+encounteredSum.get(prev));
printSequenceForZeroSum(array, i);
count++;
} else {
encounteredSum.put(prev, i);
}
}
return count;
}
public static void printSequenceForZeroSum(int[] array, int endIndex) {
int sum = array[endIndex];
while(sum!=0) {
System.out.print(array[endIndex]+ " ");
sum += array[--endIndex];
}
System.out.println(array[endIndex]);
}Stack Overflow用户
发布于 2014-08-07 04:03:00
一个逻辑类似于Fabricio答案的C++实现。
pair<int, int> FindSubsequenceSum(const vector<int>& arr)
{
map<int, int> sumMap;
map<int, int>::iterator it;
int sum = 0;
for (int i = 0; i < arr.size(); i++)
{
sum += arr[i];
it = sumMap.find(sum);
if (it != sumMap.end())
{
return make_pair(it->second + 1, i);
} else {
sumMap.insert(make_pair(sum, i));
}
}
int main()
{
int arr[] = {1,4,-3,-4,6,-7,8,-5};
vector<int> input(arr, arr + sizeof(arr) / sizeof(arr[0]));
pair<int, int> result = FindSubsequenceSum(input);
cout << "(" << result.first << "," << result.second << ")" << endl;
return 0;
}
Output:
(2,6)页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14865688
复制相关文章
相似问题
腾讯云开发者
