What is the main approach to Solve Make Array Elements Equal to Zero?

Use direct simulation from each zero element in both directions, decrementing values and checking if all elements reach zero.

Can I optimize beyond simulation for small arrays?

Since the array size is at most 100, straightforward simulation is sufficient and simple to implement correctly.

Why test both left and right directions from each zero?

Some paths reduce all elements to zero only in one direction, so checking both ensures all valid selections are counted.

How do overlapping paths affect counting valid selections?

Each starting zero and direction is evaluated independently, preventing interference from previous trials by using array copies.

Does this problem always guarantee at least one solution?

Not necessarily. There may be cases where no starting position and direction can reduce all elements to zero, yielding zero valid selections.

#3354

Easy

auto_awesome数组·模拟

LeetCode 题解工作台

使数组元素等于零

给你一个整数数组 nums 。开始时，选择一个满足 nums[curr] == 0 的起始位置 curr ，并选择一个移动方向：向左或者向右。此后，你需要重复下面的过程：如果 curr 超过范围 [0, n - 1] ，过程结束。如果 nums[curr] == 0 ，沿当前方向继续移动…

数组模拟前缀和

题目描述

给你一个整数数组 nums 。

开始时，选择一个满足 nums[curr] == 0 的起始位置 curr ，并选择一个移动方向：向左或者向右。

此后，你需要重复下面的过程：

如果 curr 超过范围 [0, n - 1] ，过程结束。
如果 nums[curr] == 0 ，沿当前方向继续移动：如果向右移，则递增 curr ；如果向左移，则递减 curr 。
如果 nums[curr] > 0:
- 将 nums[curr] 减 1 。
- 反转移动方向（向左变向右，反之亦然）。
- 沿新方向移动一步。

如果在结束整个过程后，nums 中的所有元素都变为 0 ，则认为选出的初始位置和移动方向有效。

返回可能的有效选择方案数目。

示例 1：

输入：nums = [1,0,2,0,3]

输出：2

解释：

可能的有效选择方案如下：

选择 curr = 3 并向左移动。
- [1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,1,0,3] -> [1,0,1,0,3] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,0,0,2] -> [1,0,0,0,2] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,1] -> [0,0,0,0,0].
选择 curr = 3 并向右移动。
- [1,0,2,0,3] -> [1,0,2,0,3] -> [1,0,2,0,2] -> [1,0,2,0,2] -> [1,0,1,0,2] -> [1,0,1,0,2] -> [1,0,1,0,1] -> [1,0,1,0,1] -> [1,0,0,0,1] -> [1,0,0,0,1] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [1,0,0,0,0] -> [0,0,0,0,0].

示例 2：

输入：nums = [2,3,4,0,4,1,0]

输出：0

解释：

不存在有效的选择方案。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100
至少存在一个元素 i 满足 nums[i] == 0 。

lightbulb

解题思路

方法一：枚举 + 前缀和

假设我们初始向左移动，遇到了一个非零元素，那么我们就需要将这个元素减一，然后改变移动方向，继续移动。

因此，我们可以维护每个零值元素左侧的元素和 $l$ ，右侧元素的和 $s - l$ 。如果 $l = s - l$ ，即左侧元素和等于右侧元素和，那么我们可以选择当前零值元素，向左或向右移动，答案加 $2$ ；如果 $|l - (s - l)| = 1$ ，此时如果左侧元素和更大，那么我们可以选择当前零值元素，向左移动，答案加 $1$ ，如果右侧元素和更大，那么我们可以选择当前零值元素，向右移动，答案加 $1$ 。

时间复杂度 $O(n)$ ，其中 $n$ 为数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countValidSelections(self, nums: List[int]) -> int:
        s = sum(nums)
        ans = l = 0
        for x in nums:
            if x:
                l += x
            elif l * 2 == s:
                ans += 2
            elif abs(l * 2 - s) == 1:
                ans += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n^2) in the worst case since each zero element is tried in both directions over the array. Space complexity is O(n) for temporary array copies during simulation.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Noticing the small input size implies a simulation-based solution is acceptable.
question_mark
Expecting candidates to handle edge cases where no valid selection exists.
question_mark
Looking for recognition that directional moves must be tested from each zero position.

warning

常见陷阱

外企场景

error
Overwriting the original array during simulation, corrupting other trials.
error
Failing to check both left and right directions for each zero.
error
Miscounting valid selections when multiple zeros interact in overlapping paths.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count the minimum steps to reduce all elements to zero rather than the number of valid selections.
arrow_right_alt
Allow subtracting variable values instead of fixed ones during each move.
arrow_right_alt
Extend the array length or element range to test simulation efficiency under higher constraints.

help

常见问题

外企场景

继续练习

#3494 酿造药水需要的最少总时间 #3179 K 秒后第 N 个元素的值 #3028 边界上的蚂蚁