题目

给你一个整数数组 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 。

解题思路

首先，题目描述了一个非常具体、规则有点绕的模拟过程：

从一个 0 开始。
选一个方向（左/右）。
遇到 0 就继续走。
遇到 >0 的数，就让它 -1，然后掉头，走一步。
直到走出边界。
最后，如果所有数都变成了 0，这个“起点 + 方向”的组合就是有效的。

如果我们真的去写代码模拟这个过程，会非常复杂，而且很容易出错。

解题的关键在于理解 “遇到 >0 的数，就让它 -1，然后掉头” 这句话。

这像什么呢？就像一个球在一个中心点（我们出发的 0）和左右两堵墙之间来回弹跳。

起点 0：这是我们的中心点/枢纽。
左边的数：是左边的“墙”。
右边的数：是右边的“墙”。

我们来定义两个关键变量：

L：起点 0 左边所有数字的总和。这是左墙的总“血量”。
R：起点 0 右边所有数字的总和。这是右墙的总“血量”。
Total：数组中所有数字的总和，Total = L + R。

“弹跳”的过程是这样的：

你从 0 出发，比如向右。
你会穿过所有 0，撞到右边第一个非零数。
这个数 -1（R 的总血量消耗了 1），你掉头向左。
你会穿过 0（和其他 0），撞到左边第一个非零数。
这个数 -1（L 的总血量消耗了 1），你掉头向右。
...如此循环。

这个过程的本质是：你从一个方向出发，会交替地消耗 L 和 R 的血量。

对于任何一个 nums[i] == 0 的起点，我们都有两种选择：

情况一：选择“向右”出发

消耗顺序：你先撞右墙，再撞左墙，再撞右墙... 顺序是：R, L, R, L, R, L, ...
有效条件：要让这个过程有效（清空所有数），你消耗 R 的总次数（R_hits）必须等于 R，消耗 L 的总次数（L_hits）必须等于 L。
分析消耗次数：
- 因为消耗顺序是 R, L, R, L...，所以 R_hits（撞右墙次数）和 L_hits（撞左墙次数）的关系只有两种可能：
  1. R_hits == L_hits （最后一下撞的是 L）
  2. R_hits == L_hits + 1 （最后一下撞的是 R）
推导结论：
- 要满足 R_hits == R 和 L_hits == L，同时又要满足 R_hits == L_hits 或 R_hits == L_hits + 1：
  - 如果 R_hits == L_hits，那么必须 R == L。
  - 如果 R_hits == L_hits + 1，那么必须 R == L + 1。
结论 1：“向右出发”有效的条件是：R == L 或 R == L + 1。

情况二：选择“向左”出发

消耗顺序：你先撞左墙，再撞右墙，再撞左墙... 顺序是：L, R, L, R, L, R, ...
有效条件：同样，L_hits 必须等于 L，R_hits 必须等于 R。
分析消耗次数：
- 因为消耗顺序是 L, R, L, R...，所以 L_hits 和 R_hits 的关系只有两种可能：
  1. L_hits == R_hits （最后一下撞的是 R）
  2. L_hits == R_hits + 1 （最后一下撞的是 L）
推导结论：
- 要满足 L_hits == L 和 R_hits == R，同时又要满足 L_hits == R_hits 或 L_hits == R_hits + 1：
  - 如果 L_hits == R_hits，那么必须 L == R。
  - 如果 L_hits == R_hits + 1，那么必须 L == R + 1。
结论 2：“向左出发”有效的条件是：L == R 或 L == R + 1。

现在我们把两个结论合起来看，对于任意一个 0 点：

如果 L == R：
- “向左出发”有效（满足 L == R）。
- “向右出发”有效（满足 R == L）。
- 这个 0 点贡献 2 个有效方案。
如果 L == R + 1：
- “向左出发”有效（满足 L == R + 1）。
- “向右出发”无效（既不满足 R == L 也不满足 R == L + 1）。
- 这个 0 点贡献 1 个有效方案。
如果 R == L + 1：
- “向左出发”无效。
- “向右出发”有效（满足 R == L + 1）。
- 这个 0 点贡献 1 个有效方案。
如果 abs(L - R) > 1：
- 两种出发方式都无效。
- 这个 0 点贡献 0 个有效方案。

我们可以把第 2 和第 3 点合并为：如果 abs(L - R) == 1，则贡献 1 个有效方案。

我们不需要真的在每个 0 点都去重新计算 L 和 R。我们可以用一个更高效的方法：

第一遍遍历：计算出数组的总和 total。
第二遍遍历：
- 用一个变量 pre 记录“前缀和”（也就是 L）。
- 开始遍历数组：
  - 如果 nums[i] > 0：说明这个数在“左墙”上，累加到 pre，即 pre += nums[i]。
  - 如果 nums[i] == 0：说明我们找到了一个起点！
    - 此时，L = pre。
    - R 是多少？R = total - L = total - pre。
    - 现在我们套用第 4 步的规律：
      - 检查 L == R：即 pre == total - pre，简化为 pre * 2 == total。如果成立，ans += 2。
      - 检查 abs(L - R) == 1：即 abs(pre - (total - pre)) == 1，简化为 abs(pre * 2 - total) == 1。如果成立，ans += 1。
遍历结束后，返回 ans。

这就是解法的完整思路。它把一个复杂的动态模拟问题，转换成了一个基于前缀和的静态数学判断问题。

具体代码

func countValidSelections(nums []int) (ans int) {
	total := 0
	for _, x := range nums {
		total += x
	}

	pre := 0
	for _, x := range nums {
		if x > 0 {
			pre += x
		} else if pre*2 == total {
			ans += 2
		} else if abs(pre*2-total) == 1 {
			ans++
		}
	}
	return ans
}

func abs(x int) int { if x < 0 { return -x }; return x }

3354. 使数组元素等于零

beautifulremi

题目

解题思路

具体代码