/
sliding_window.rs
76 lines (63 loc) · 2.09 KB
/
sliding_window.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
pub struct Solution;
// ------------------------------------------------------ snip ------------------------------------------------------ //
use std::cmp::Ordering;
#[derive(Default)]
struct Window {
start: usize,
length: usize,
sum: u32,
}
impl Window {
fn slide(&mut self, arr: &[i32], target: u32, num: u32) -> bool {
self.sum += num;
self.length += 1;
loop {
match self.sum.cmp(&target) {
Ordering::Less => break false,
Ordering::Equal => break true,
Ordering::Greater => {
self.sum -= arr[self.start] as u32;
self.start += 1;
self.length -= 1;
}
}
}
}
}
impl Solution {
fn inner(arr: &[i32], target: u32) -> usize {
let mut right_window = Window::default();
let mut left_window = Window::default();
let mut min_left_length = usize::MAX;
let mut result = usize::MAX;
for &right_num in arr {
if right_window.slide(arr, target, right_num as _) {
for &left_num in &arr[left_window.start + left_window.length..right_window.start] {
if left_window.slide(arr, target, left_num as _) {
min_left_length = min_left_length.min(left_window.length);
}
}
if let Some(new_result) = min_left_length.checked_add(right_window.length) {
result = result.min(new_result);
}
}
}
result
}
pub fn min_sum_of_lengths(arr: Vec<i32>, target: i32) -> i32 {
Self::inner(&arr, target as _) as _
}
}
// ------------------------------------------------------ snip ------------------------------------------------------ //
impl super::Solution for Solution {
fn min_sum_of_lengths(arr: Vec<i32>, target: i32) -> i32 {
Self::min_sum_of_lengths(arr, target)
}
}
#[cfg(test)]
mod tests {
#[test]
fn test_solution() {
super::super::tests::run::<super::Solution>();
}
}