2025-06-07：零数组变换Ⅰ。用go语言，给定一个长度为 n 的整数数组 nums，以及一个二维数组 queries，每个查询 queries[i] 表示一个区间 [li, ri]。

对于每个查询，允许从 nums 的区间 [li, ri] 内选择任意多个索引，将这些索引对应的元素的值各减 1。

如果按顺序依次执行所有查询操作后，最终能够使数组 nums 中所有元素都变为 0，则返回 true；否则返回 false。

1 <= nums.length <= 100000。

0 <= nums[i] <= 100000。

1 <= queries.length <= 100000。

queries[i].length == 2。

0 <= li <= ri < nums.length。

输入： nums = [1,0,1], queries = [[0,2]]。

输出： true。

解释：

对于 i = 0：

选择下标子集 [0, 2] 并将这些下标处的值减 1。

数组将变为 [0, 0, 0]，这是一个零数组。

题目来自力扣3355。

解决思路

1. 差分数组技术：

   • 差分数组是一种高效处理区间增减操作的数据结构。对于每个查询 [li, ri]，我们可以标记这些区间的覆盖次数。
   • 具体来说，我们可以使用一个差分数组 deltaArray，其长度为 len(nums) + 1。对于每个查询 [li, ri]，我们执行：
     • deltaArray[li] += 1
     • deltaArray[ri + 1] -= 1
   • 然后，通过计算差分数组的前缀和，可以得到每个位置被查询覆盖的次数 operationCounts[i]。

2. 验证操作次数是否足够：

   • 对于 nums 中的每个元素 nums[i]，它必须满足 operationCounts[i] >= nums[i]。因为每个查询可以覆盖 i 时，最多只能减1，所以 nums[i] 需要至少被覆盖 nums[i] 次才能减到0。
   • 如果所有 nums[i] 都满足 operationCounts[i] >= nums[i]，则返回 true；否则返回 false。

具体步骤

1. 初始化差分数组：

   • 创建一个长度为 len(nums) + 1 的差分数组 deltaArray，初始化为0。
   • 对于每个查询 [li, ri]：
     • deltaArray[li] += 1
     • deltaArray[ri + 1] -= 1

2. 计算操作覆盖次数：

   • 创建一个数组 operationCounts，其长度为 len(deltaArray)。
   • 初始化 currentOperations = 0。
   • 遍历 deltaArray，对于每个位置 i：
     • currentOperations += deltaArray[i]
     • operationCounts[i] = currentOperations
   • 这样，operationCounts[i] 表示索引 i 被查询覆盖的次数。

3. 验证是否可以减到0：

   • 遍历 nums 的每个元素 nums[i]：
     • 如果 operationCounts[i] < nums[i]，说明无法通过操作将 nums[i] 减到0，直接返回 false。
   • 如果所有元素都满足 operationCounts[i] >= nums[i]，则返回 true。

时间复杂度和空间复杂度

• 时间复杂度：
  • 初始化差分数组：O(1)（因为直接创建并初始化为0）。
  • 处理所有查询：O(Q)，其中 Q 是查询的数量。
  • 计算操作覆盖次数：O(N)，其中 N 是 nums 的长度。
  • 验证操作次数：O(N)。
  • 总时间复杂度：O(Q + N)。
• 空间复杂度：
  • 差分数组 deltaArray：O(N)。
  • 操作覆盖次数数组 operationCounts：O(N)。
  • 总额外空间复杂度：O(N)。

Go完整代码如下：

package main

import (
	"fmt"
)

func isZeroArray(nums []int, queries [][]int) bool {
	deltaArray := make([]int, len(nums)+1)
	for _, query := range queries {
		left := query[0]
		right := query[1]
		deltaArray[left] += 1
		deltaArray[right+1] -= 1
	}
	operationCounts := make([]int, len(deltaArray))
	currentOperations := 0
	for i, delta := range deltaArray {
		currentOperations += delta
		operationCounts[i] = currentOperations
	}
	for i := 0; i < len(nums); i++ {
		if operationCounts[i] < nums[i] {
			return false
		}
	}
	return true
}

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

Python完整代码如下：

.

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

def is_zero_array(nums, queries):
    n = len(nums)
    delta_array = [0] * (n + 1)
    for left, right in queries:
        delta_array[left] += 1
        if right + 1 < len(delta_array):
            delta_array[right + 1] -= 1

    operation_counts = [0] * n
    current_operations = 0
    for i in range(n):
        current_operations += delta_array[i]
        operation_counts[i] = current_operations

    for i in range(n):
        if operation_counts[i] < nums[i]:
            return False
    return True


if __name__ == "__main__":
    nums = [1, 0, 1]
    queries = [[0, 2]]
    print(is_zero_array(nums, queries))