2025-06-06：使数组元素等于零。用go语言，给定一个整数数组 nums。 起始时，你需要选择一个索引 curr，要求 n

2025-06-06：使数组元素等于零。用go语言，给定一个整数数组 nums。

起始时，你需要选择一个索引 curr，要求 nums[curr] = 0，并选择一个移动方向（向左或向右）。

接下来按照以下步骤进行：

1. 1. 若 curr 越界（curr < 0 或 curr >= n），过程结束。
2. 2. 若当前位置的 nums[curr] 为 0，则根据当前方向移动一步（向右时 curr 加一，向左时 curr 减一）。
3. 3. 若当前位置的 nums[curr] 大于 0，则将 nums[curr] 减一，切换移动方向（左变右，右变左），然后沿新的方向移动一步。

当整个过程结束时，如果数组 nums 中所有元素均为 0，则说明该起始位置和方向是有效的。

请返回所有可能的有效起始位置和方向的组合数量。

1 <= nums.length <= 100。

0 <= nums[i] <= 100。

至少存在一个元素 i 满足 nums[i] == 0 。

输入：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].

题目来自力扣3354。

分步骤过程描述

1. 初始化

• • 遍历数组，找到所有 nums[i] == 0 的索引 i，这些是可能的起始位置 curr。
• • 对于每个起始位置 curr，尝试两个方向（左、右）。

2. 模拟移动过程

对于每个 (curr, direction) 组合：

• • 复制数组：为了避免修改原数组，需要复制一份 nums 进行操作。
• • 初始化方向：记录当前方向（左或右）。
• • 循环移动：
  • • 越界检查：如果 curr 越界，结束循环。
  • • 零值处理：
    • • 如果 nums[curr] == 0，按当前方向移动一步。
  • • 非零值处理：
    • • 如果 nums[curr] > 0，将其减 1，切换方向，然后按新方向移动一步。
• • 终止条件：
  • • 如果 curr 越界，检查数组中是否所有元素均为 0。
  • • 如果是，则该 (curr, direction) 组合有效。

3. 检查有效性

• • 每次移动后，可以提前检查是否所有元素均为 0（但题目要求过程结束时才检查）。
• • 如果模拟结束后所有元素为 0，则计数加 1。

4. 统计结果

• • 对所有可能的 (curr, direction) 组合进行模拟，统计有效的组合数量。

时间复杂度和空间复杂度

• • 时间复杂度：
  • • 最坏情况下，每次 (curr, direction) 组合需要遍历整个数组多次（每次移动可能减少一个非零元素）。
  • • 设数组长度为 n，最大值为 m，则时间复杂度为 O(n * m * n) = O(n² * m)。
• • 空间复杂度：
  • • 需要复制数组进行模拟，空间复杂度为 O(n)（每次模拟时复制数组）。
  • • 如果递归实现（如 DFS），栈空间为 O(n)。

Go完整代码如下：

package main

import (
    "fmt"
)

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
        } elseif pre*2 == total {
            ans += 2
        } elseif abs(pre*2-total) == 1 {
            ans++
        }
    }
    return ans
}

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

func main() {
    nums := []int{1, 0, 2, 0, 3}
    fmt.Println(countValidSelections(nums))
}

Python完整代码如下：

# -*-coding:utf-8-*-

defcount_valid_selections(nums):
    ans = 0
    total = sum(nums)

    pre = 0
    for x in nums:
        if x > 0:
            pre += x
        elif pre * 2 == total:
            ans += 2
        elifabs(pre * 2 - total) == 1:
            ans += 1
    return ans

if __name__ == '__main__':
    nums = [1, 0, 2, 0, 3]
    print(count_valid_selections(nums))