子序列和

Question

给定一个整数数组，如[1, 2, -3, 1]，查找是否存在一个子序列的总和为0，并返回它（例如[1, 2, -3]或[2, -3, 1]）。
检查每个子序列的时间复杂度是O(n^2)，效率太低。有什么改进的想法吗？

- user1762571

---

我会在这里发布：http://cs.stackexchange.com/。顺便说一句，我不认为检查每个子序列的时间复杂度是O(n^2)。它应该是指数级别的O(2^n)。你所说的O(n^2)更适用于在线方法。 - A.B.

如果它们是连续的子序列，则有n-1*n-2个组合。 - argentage

连续的子序列？还是任意的子序列？严格来说，“子序列”这个术语并不意味着连续性。你的例子并不具有决定性。 - AnT stands with Russia

非连续版本是http://en.wikipedia.org/wiki/Knapsack_problem，被认为是NP问题，我相信你知道。根据暴力计算的边界，我假设它不是那个问题。 - argentage

如果您发现我的答案解决了您的问题，能否请您接受它呢？ - argentage

Answer 1

创建一个新的数组，其中每个元素均等于前面所有元素的和再加上当前元素。

输入：

1  4 -3 -4  6  -7  8 -5

Becomes:

1  5  2  -2  4  -3  5  0
   ^                ^

然后查找结果数组中匹配的元素。

由于这些代表函数整体变化为零的位置，你会发现如果它们的位置是i和k，则子序列(i+1，k)是一个零和子序列。(在这种情况下，[2:6]).

此外，表格中的任何零都表示子序列(0，k)是一个零和子序列。使用哈希表或其他快速碰撞定位器进行查找可以使其O(N)执行。

- argentage

---

很好。您能否提供关于此特定解决方案的链接或文献？此问题和/或解决方案有正式名称吗？ - istepaniuk

创建运行总和数组不是n^2时间吗？ - user4256874

不行，因为从0到n+1的和与从0到n加上n+1的和是相同的，这个性质非常方便。 - argentage

子序列与子数组不同。不确定为什么没有经过验证就被接受为正确答案。举个例子：1,2,3,3,4,-5，其中前缀和是1,3,6,9,13,8。 - everlasto

我不确定你的意思；如果你指的是“从数组中获取任意元素，即使它们不是连续的”作为子序列，那么这是一个NP问题（正如我在问题评论中所述）。由于原帖作者将朴素解决方案称为O(N^2)，我认为他们并不想要那个。 - argentage

Answer 2

在哈希表中进行累加，并将累加值与数组索引一起存储。

如果您曾经得到一个已经出现过的累加值，则返回哈希表中索引值+1，以及当前索引值。此解决方案时间复杂度为O(n)。

不需要新的数组。由于哈希表，空间复杂度为O(N)。

---

Python实现代码：

input = [1, 4, -3, -4, 6, -7, 8, -5]
map = {}
sum = 0
for i in range(len(input)):
    sum += input[i]
    if sum in map:
        print map[sum][0] + 1, "to", i
    map[sum] = (i, sum)

请注意，重复的子序列将不会被显示。例如：如果（1到2）是一个子序列，而（3到4）、（1到4）将不会被显示。您可以通过在Map的每个位置存储列表来实现此行为：

for x in map[sum]:
    print x[0]+1, "to", i
map[sum].append((i, sum))

- Rudolf Real

---

你忽略了哈希表所需的空间。为了实现高效的哈希表行为，它必须比可能值的集合更大。 - nneonneo

@nneonneo 确认，已添加。 - Rudolf Real

Answer 3

以下是@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]);
}

- Bhumik Thakkar

Answer 4

一个 C++ 实现，其逻辑类似于 Fabricio 的答案。

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)

- Bikash

Answer 5

一个Scala实现：

List(1,2,3,4).scan(0){_+_}

结果将会是List(0, 1, 3, 6, 10)。

或者你可以：

List(1,2,3,4).scan(0){_+_}.tail  

获取List(1, 3, 6, 10)

- zeffer