时间轴

2025-10-28

init

题目：

P3354 使数组元素等于零

https://leetcode.cn/problems/make-array-elements-equal-to-zero/description/?envType=daily-question&envId=2025-10-28

依照题意，如果选择的 index 左边的所有和与右边的所有数和相同，那么往左走往右走都可以。如果左边比右边大 1 或者右边比左边大 1，那么只能选择大的那一边。利用前缀和快速求解数组元素的和。

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
struct Solution;

impl Solution {
    pub fn count_valid_selections(nums: Vec<i32>) -> i32 {
        let mut scheme = 0;
        let mut vec: Vec<i32> = Vec::with_capacity(nums.len()); // 计算前缀和
        let mut last = 0;
        for &val in nums.iter() {
            last = last + val;
            vec.push(last);
        }

        let total = if let Some(&sum) = vec.last() { sum } else { 0 };

        for (index, &val) in nums.iter().enumerate() {
            if val == 0 {
                let left_sum = if let Some(&sum) = vec.get(index - 1) {
                    sum
                } else {
                    0
                };
                let right_sum = if let Some(&sum) = vec.get(index) {
                    total - sum
                } else {
                    0
                };
                if left_sum == right_sum {
                    scheme += 2;
                } else if left_sum == right_sum + 1 || right_sum == left_sum + 1 {
                    scheme += 1;
                }
            }
        }
        scheme
    }
}