/
sliding_window.rs
75 lines (59 loc) · 1.91 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
pub struct Solution;
// ------------------------------------------------------ snip ------------------------------------------------------ //
use std::collections::VecDeque;
impl Solution {
pub fn num_subarrays_with_sum(nums: Vec<i32>, goal: i32) -> i32 {
let goal = goal as u32 as usize;
let mut queue = VecDeque::with_capacity(goal);
let mut iter = (0_u32..).zip(nums);
while queue.len() < goal {
loop {
if let Some((i, num)) = iter.next() {
if num != 0 {
queue.push_back(i);
break;
}
} else {
return 0;
}
}
}
if let Some(&leading_zeros) = queue.front() {
let mut factor = leading_zeros + 1;
let mut result = factor;
for (i, num) in iter {
if num != 0 {
let removed = queue.pop_front().unwrap();
queue.push_back(i);
factor = *queue.front().unwrap() - removed;
}
result += factor;
}
result as _
} else {
let mut result = 0;
let mut prev_1 = u32::MAX;
for (i, num) in iter {
if num == 0 {
result += i.wrapping_sub(prev_1);
} else {
prev_1 = i;
}
}
result as _
}
}
}
// ------------------------------------------------------ snip ------------------------------------------------------ //
impl super::Solution for Solution {
fn num_subarrays_with_sum(nums: Vec<i32>, goal: i32) -> i32 {
Self::num_subarrays_with_sum(nums, goal)
}
}
#[cfg(test)]
mod tests {
#[test]
fn test_solution() {
super::super::tests::run::<super::Solution>();
}
}