Problem
We need to find a maximum length slice (contiguous sub-vector) with a provided sum of the elements in a given vector vec.
Example 1:
Input: vec = [5, 6, -5, 5, 3, 4, 1], sum = 7
Output: [-5, 5, 3, 4]
Explanation: This is the longest slice (length = 4) that has a sum of the elements equals to 7.
Example 2:
Input: vec = [5, 6, -5, 5, 3, 4, 1], sum = 5
Output: [4, 1]
Explanation: This is the longest slice (length = 2) that has a sum of the elements equals to 5.
Example 3:
Input: vec = [1, 2, 3], sum = 10
Output: None
Explanation: There are no slices having a sum of the elements equals to 10.
Solution
fn find_max_length_slice_with_given_sum(vec: &Vec<i32>, sum: i32) -> Option<&[i32]> {
let mut map: HashMap<i32, usize> = HashMap::from([(0, 0)]);
let mut max_length: usize = 0;
let mut max_length_start_index: Option<usize> = None;
let mut max_length_end_index: Option<usize> = None;
let mut current_sum: i32 = 0;
for (index, elem) in vec.iter().enumerate() {
current_sum += *elem;
if let Some(start_position) = map.get(&(current_sum - sum)) {
let length: usize = index - start_position + 1;
if length > max_length {
max_length = length;
max_length_start_index = Some(*start_position);
max_length_end_index = Some(index);
}
}
map.entry(current_sum).or_insert(index + 1);
}
match (max_length_start_index, max_length_end_index) {
(Some(start), Some(end)) => Some(&vec[start..end + 1]),
_ => None,
}
}
Explanation
The solution is similar to what we implemented in Rust Interview Puzzles: Check if a slice with 0 sum exists in a vector but slightly more complex. We iterate over the vector vec and on each iteration update current_sum of the elements (this current_sum is later saved to the map we created earlier, together with the current index + 1 value). Then we check if current_sum - sum value has already been saved to the map earlier. If it was, then it means that at some point earlier we had current_sum which was equal to current_sum value which we have now (minus the target value sum provided to the function). In other words, the difference between the earlier current_sum value and the current_sum value that we have now is exactly sum (which means we've found the slice with the given sum as per the requirement). Then we just need to make sure the slice we found is the longest one, so we need to compare it with the current longest slice we have had so far. If length we found is larger than the current max_length, then we update the max_length and also save the starting and the ending index of the current longest slice (max_length_start_index, max_length_end_index).
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 HashMap we used.