Problem
We need to check if an unsorted vector of numbers vec contains a contiguous sub-vector (slice) of 0 sum.
Example 1:
Input: vec = [4, 2, -3, 1, 6]
Output: true
Explanation: Because it contains a contiguous sub-vector [2, -3, 1].
Example 2:
Input: vec = [4, 2, 0, 1, 6]
Output: true
Explanation: Because it contains [0].
Example 3:
Input: vec = [-3, 2, 3, 1, 6]
Output: false
Explanation: Though it contains a sub-vector [-3, 3], but it's not contiguous.
Solution
fn check_if_slice_with_0_exists(vec: &Vec<i32>) -> bool {
let mut set = HashSet::from([0]);
let mut sum = 0;
for e in vec {
sum = sum + e;
if set.contains(&sum) {
return true;
} else {
set.insert(sum);
}
}
return false;
}
Explanation
We iterate over the vector vec, accumulating sum of the vector values e along the way. And on each iteration we check if the current sum of the elements is in the HashSet set we created earlier. If the sum is not yet in the set, then we just add it to the set. If it is in the set, then we immediately return true as a result. The idea here is that if we encounter again a sum value that we've seen already before (the value that is already in the set), it means that after we saw that sum value for the first time, further elements added to the sum negated that original sum value, so that we encountered the same value again. That is only possible if the vector contains a contiguous sub-vector with 0 sum.
Complexity
The time complexity of this solution is O(n) (n is a size of the input vector). Also the solution requires O(n) extra space for the HashSet we created.