小于O(n2)的负数和正数的子数组和等于k

Question

我可以搜索eqaul到k之和的子数组中的正数，但下面的代码无法搜索数组中的负数。对于数组中的负数和正数，有没有找到给定和的子数组的算法？

public static void subarraySum(int[] arr, int sum) {

    int start=0;
    int currSum=arr[0];

    for(int i = 1;i<=arr.length;i++) {
        while(currSum>sum ) {
            currSum-=arr[start];
            start++;
        }
        if(currSum==sum) {
            System.out.println(start + " " + (i-1) + " index");
            start=i;
            currSum=0;
        }
        if(i<arr.length) {
            currSum +=arr[i];
        }

    }
}

例如，{10,2,-2,-20,10}，在这个数组中查找sum为-10的子数组。子数组在这种情况下是{-20,10}。

Answer 1

对于每个索引i预先计算从0到i的子数组之和。然后要找到任何子数组(i,j)的和，只需计算sum[j]-sum[i]+arr[i]。

  public static void subArraySum(int[] arr, int target) {
    if (arr.length == 0) return;

    int n = arr.length;
    int[] sum = new int[n];
    sum[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        sum[i] = sum[i - 1] + arr[i];
    }

    for (int i = 0; i < n; ++i)
      for (int j = i; j < n; ++j)
        if (sum[j] - sum[i] + arr[i] == target) {
            System.out.println(i + " " + j);
        }
  }

如果将总和存储在映射中，然后查询该映射以获得所需的总和，则可以更快地找到子数组。

 public static void subArraySum(int[] arr, int target) {
  if (arr.length == 0) return;

  int n = arr.length;
  int[] sum = new int[n];
  sum[0] = arr[0];
  for (int i = 1; i < n; ++i) {
      sum[i] = sum[i - 1] + arr[i];
  }

  Map<Integer, Integer> map = new TreeMap<>();
  for (int i = 0; i < n; ++i) {
      if (sum[i] == target) {
          System.out.println(0 + " " + i);
      }

      int requiredSum = sum[i] - target;
      if (map.containsKey(requiredSum)) {
          int startIndex = map.get(requiredSum) + 1;
          System.out.println(startIndex + " " + i);
      }
      map.put(sum[i], i);
  }
}

这个解决方案是O(N*logn)，但是如果使用HashMap而不是TreeMap(O(N)，如果您假设HashMap操作的复杂性是恒定的），则可以使其更快。