Zero Sum Subarray

mediumSave

ArrayHash TablePrefix Sum

Given an array of integers, find if it contains a contiguous subarray which sums to zero. Return true if such a subarray exists, otherwise, return false.

Example 1

Input

[
  [
    1,
    2,
    -3,
    3
  ]
]

Output

true

Explanation. The subarray [2, -3] sums to zero.

Example 2

Input

Output

true

Explanation. The subarray [2, -2] sums to zero.

Example 3

Input

Output

false

Explanation. There is no subarray that sums to zero.

Example 4

Input

[
  [
    0
  ]
]

Output

true

Explanation. The subarray [0] itself sums to zero.

Follow-up: Can you solve the problem in O(n) time complexity using extra space efficiently?

Constraints:

The input array may contain both positive and negative integers. It will not be empty and will contain at least one element.

Views: 3