CODEWITHSUNDEEP
arraysalgorithm
Akash Magoon
Akash Magoon

Reputation: 899

Is there a subarray that sums to a target?

Popular interview question:

Given an array of positive integers and a target integer, find if there is a consecutive subarray that sums to the target.

E.g.

Array = [1,3,6,7,8,10] Target = 16 The subarray that sums to 16 is [3,6,7], so it returns true.

Upvotes: 5

Views: 1176

Answers (2)

Lingxi
Lingxi

Reputation: 14967

This one goes linear time (C++ code).

bool Test(const int* arr, int size, int target) {
  if (target < 0) return false;
  int acc = 0;
  int i = 0, j = 0;
  while (acc != target) {
    if (acc < target) {
      if (j == size) break;
      acc += arr[j++];
    }
    else {
      acc -= arr[i++];
    }
  }
  return acc == target;
}

Note that the pre-check for a negative target value is necessary to guarantee the loop invariant that i <= j. Specifically, when i == j, acc will be 0, and a positive target guarantees that the branch under if (acc < target) is hit.

Upvotes: 7

Akash Magoon
Akash Magoon

Reputation: 899

Just wrote and fully tested. Two methods, hasConsec (where most of the logic is) and sumArr (helper method that sums values in an array). hasConsec and uses 2 indexes, first and last, to create subarrays. The helper method is used to sum the subarray created and then hasConsec checks if it matches the target, if it's greater than the target, or if it's less than the target. If it matches, it returns true; if the sum is less than the target, the last index is incremented; if it's greater than the target, then first index is incremented. Repeat until the first index is equal to the length of the array. If that happens, there's no subarray that sums to the target. Return false;

public static boolean hasConsec(int arr[], int target) {
    int first = 0, last = 0;

    while (last <  arr.length) {
        int sub[] = Arrays.copyOfRange(arr, first, last);
        int subSum = sumArr(sub);
        if (subSum == target) 
             return true;
        else if (subSum < target)
             last++;
        else {
            if (++first < last)
                last = first;
         }
     }
    return false;
}

public static int sumArr(int arr[]) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) 
        sum += arr[i];
     return sum;
 }

Upvotes: 1

Related Questions