subarray sum

Question:

Given an array in arbitrary order, find if there exists a contiguous subarray sum up to the target.

Example:

arr = [5, 1, 3, 7, 21]

target = 1
output: true

target = 4
output = true

target = 8
output = false

target = -10 (hint that the array may include negative number)
output = false


 Solution:

// brute-force  O(n^3)
boolean findTarget(int[] arr, int target) {
  for (int i = 0; i < arr.size(); i++) {
    for (int j = i + 1; j < arr.size(); j++) {
      int sum = 0;
      for (int k = i; i <= j; i++) {
        sum += arr[k];
        if (sum == target) {
          return true;
        }
      }
    }
  }
  return false;
}

// optimized brute-force O(n^2)
boolean findTarget(int[] arr, int target) {
  for (int i = 0; i < arr.size(); i++) {
    int sum = 0;
    for (int j = i; j < arr.size(); j++) {
      sum += arr[i];
      if (sum == target) {
       return true;
      }
    }
  }
  return false;
}

// hashset time O(n) space O(n)
boolean findTarget(int[] arr, int target) {
  HashSet<Integer> set = new Hashset();
  int sum = 0;
  for (int i = 0; i < arr.size(); i++) {
   if (set.has(sum - target)) {
      return true;
    }
    set.add(sum);
  }
  return false;
}

// sliding window (assume array only have non-negative numbers)
boolean findTarget(int[] arr, int target) {
  int left = 0;
  int right = 0;
  int sum = 0;
  while (left <= right && right < arr.size()) {
    sum += arr[right];
    right += 1;
   while (sum > target && left < right) {
      sum -= arr[left];
      left += 1;
    }
    if (sum == target) {
      return true;
    }
  }
  return false;
}