Given a sequence of positive integers seq and an integer total,

return whether a contiguous sequence of seq sums up to total

Example

[1, 3, 5, 23], 8 # True (because 3 + 5 = 8)

[1, 3, 5, 23], 7 # False

[1, 6, 11], 12 # False (1 + 11 = 12 but they are not contiguous.)

Solution 1: Set O(n); O(n)

  public static boolean findSubarraySumToTarget(int[] nums, int total) {
    Set<Integer> set = new HashSet<>();
    set.add(0);
    int sum = 0;
    for (int num : nums) {
      sum += num;
      if (set.contains(sum - total)) {
        return true;
      }
      set.add(sum);
    }
    return false;
  }