Follow

Follow

# Rust Interview Puzzles: Find the longest slice with a given sum in a vector

go4fun.fun
·Nov 29, 2022·

### 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.

Rust Playground with this code