21

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

4

5 回答 5

38

创建一个新数组，其中每个元素等于先前元素的总和加上那个元素。

输入：

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) 执行。

于 2013-02-14T01:15:10.680 回答
12

进行运行求和，将总和值与数组索引一起存储在哈希表中

如果你得到一个你已经看到的总和值，返回 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）将不会显示。您可以通过在地图的每个位置存储列表来实现此行为：

for x in map[sum]:
    print x[0]+1, "to", i
map[sum].append((i, sum))
于 2014-05-27T22:41:44.713 回答
2

以下是@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]);
}
于 2014-10-15T21:05:08.600 回答
0

具有与 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)
于 2014-08-06T20:03:00.127 回答
0

一个scala实现： 

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

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

或者您可以：

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

获取列表（1、3、6、10）

于 2019-07-04T12:26:47.767 回答