Subarray sum equal to k for negative and positive numbers in less than O(n2)

Question

I can search for subarrays with sum eqaul to k for positive numbers but the below code fails for negative numbers in arrays. Is there an algorithm for finding subarrays with a given sum for negative and positive numbers in an array ?

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];
        }

    }
}

For example, {10, 2, -2, -20, 10}, find subarray with sum -10 in this array. Subarray in this case would be {-20, 10}.

So the subarray would consist out of 10 and -20 if I understood that right — Alexander Heim
Your question is not clear to me. But probably you can check here. stackoverflow.com/questions/45066119/… — procrastinator

Hypuk Hypuk · Accepted Answer · 2017-09-06T14:09:19

`O(N^2)` solution

For each index i precalculate the sum of subarray from 0 to i, inclusively. Then to find sum of any subarray (i, j) you can just calculate 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);
        }
  }

Faster solution

You can find subarray faster if you will store the sums in the map and then query this map for the required sum.

 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);
  }
}

This solution is O(N*logN), but you can make it faster if you will use HashMap instead of TreeMap (O(N) if you assume that HashMap operations complexity is constant).

Note that this solution will not print all possible pairs. If you need to find all subarrays with given sum you need to have Map<Integer, Array<Integer>> instead of Map<Integer, Integer> and store all indexes with given sum.

Subarray sum equal to k for negative and positive numbers in less than O(n2)

1 Answers

O(N^2) solution

Faster solution

`O(N^2)` solution