arrays - 查找和 k 的数组的所有连续子序列

Question

例子：

数组如下：-4 -10 -15 - 20 100 -67 47 20和 k = 51

预期输出：

-4 -10 -15 - 20 100

-4 -10 -15 - 20 100 -67 47 20

用 O(n^2) 尝试了蛮力解决方案。任何人都可以提出一个更好的解决方案吗？

Answer 1

我们可以在O(nlogn).

我们先解决一个简单的问题：

For an array, find two elements in the array which sum is k.

所以，我们可以这样做：

algo_1

pre = []
for(int i = 0; i < array.length; i++) {
  if pre.elementValueIs(k - array[i])
     output()
  pre.add(array[i])
}

通过 BST(Java.util.Map, C++ map, Python dict) 或二分查找，我们可以pre.elementValueIs在O(logn)

所以在总结中，我们可以得到一个O(nlogn)算法。

对于你的问题，我们制作了另一个新数组 s[]，它

s[i] = a[i] + a[i - 1] + ... + a[0]

因此，如果a[p] + a[p + 1] ... + a[q] = k(p<=q), s[q] - s[p - 1]= k。

这样，我们可以解决您的问题algo_1。

我为您编写了一个 Java 代码，您可以对其进行调试以获取更多详细信息：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created by Sayakiss on 8/13/15.
 */
public class SubSum {

    static class SumArray {
        private int[] sumArray;

        public SumArray(int[] inputArray) {
            sumArray = new int[inputArray.length + 1];
            sumArray[0] = 0;
            for(int i = 0; i < inputArray.length; i++) {
                sumArray[i + 1] = inputArray[i] + sumArray[i];
            }
        }

        //get input sum(array[i]) (begin<=i<=end)
        public int getSum(int begin, int end) {
            return sumArray[end + 1] - sumArray[begin];
        }
    }

    static void printResult(int[] array, int begin, int end) {
        for(int i = begin; i<= end; i++) {
            System.out.print(array[i]);
            if (i != end) {
                System.out.print(", ");
            }
        }
        System.out.println();
    }

    public static void subSum(int[] inputArray, int k) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();//sum(a[0..i]) = key
        List<Integer> list = new ArrayList<>();
        list.add(0);
        map.put(0, list);

        SumArray sumArray = new SumArray(inputArray);
        for(int i = 0; i < inputArray.length; i++) {
            int sum = sumArray.getSum(0, i);
            List<Integer> beginIndexList = map.get(k - sum);
            if (beginIndexList != null) {
                for(int beginIndex : beginIndexList)
                    printResult(inputArray, beginIndex, i);
            }
            List<Integer> integerList = map.get(sum);
            if (integerList == null) {
                integerList = new ArrayList<>();
                map.put(sum, integerList);
            }
            integerList.add(i);
        }
    }
    public static void main(String args[]) {
        subSum(new int[]{-4, -10, -15, -20, 100, -67, 47, 20}, 51);
    }
}

如果你运行我的 main 函数，你会得到输出（和你的测试用例一样）：

-4, -10, -15, -20, 100
-4, -10, -15, -20, 100, -67, 47, 20