What is the core pattern in Apply Operations to Make All Array Elements Equal to Zero?

The core pattern is combining greedy subarray reduction with a prefix sum to track cumulative operations efficiently.

How does the prefix sum approach optimize this array problem?

It reduces repeated subarray updates to a single cumulative operation, allowing O(n) time instead of O(n*k).

Can this method handle k equal to the array length?

Yes, the approach correctly applies operations once across the full array and checks if all elements reach zero.

What happens if some elements are initially zero?

Prefix sum tracking accounts for existing zeros, skipping unnecessary operations while still reducing others to zero.

Is there a risk of negative numbers with this approach?

Since the problem restricts nums to non-negative values, the difference array only tracks positive operations, avoiding negative results.

#2772

Medium

auto_awesome前缀和

LeetCode 题解工作台

使数组中的所有元素都等于零

Name: Interview AiBox
Availability: InStock
Rating: 4.9 (10000 reviews)

给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。你可以对数组执行下述操作任意次：从数组中选出长度为 k 的任一子数组，并将子数组中每个元素都减去 1 。如果你可以使数组中的所有元素都等于 0 ，返回 true ；否则，返回 false 。子数组是数组中的一个非空…

数组前缀和

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。

你可以对数组执行下述操作 任意次 ：

从数组中选出长度为 k 的任一子数组，并将子数组中每个元素都减去 1 。

如果你可以使数组中的所有元素都等于 0 ，返回 true ；否则，返回 false 。

子数组 是数组中的一个非空连续元素序列。

示例 1：

输入：nums = [2,2,3,1,1,0], k = 3
输出：true
解释：可以执行下述操作：
- 选出子数组 [2,2,3] ，执行操作后，数组变为 nums = [1,1,2,1,1,0] 。
- 选出子数组 [2,1,1] ，执行操作后，数组变为 nums = [1,1,1,0,0,0] 。
- 选出子数组 [1,1,1] ，执行操作后，数组变为 nums = [0,0,0,0,0,0] 。

示例 2：

输入：nums = [1,3,1,1], k = 2
输出：false
解释：无法使数组中的所有元素等于 0 。

提示：

1 <= k <= nums.length <= 10⁵
0 <= nums[i] <= 10⁶

lightbulb

解题思路

方法一：差分数组 + 前缀和

我们先考虑 $nums$ 的第一个元素 $nums[0]$ ：

如果 $nums[0] = 0$ ，那么我们可以不用操作；
如果 $nums[0] \gt 0$ ，那么我们需要对 $nums[0..k-1]$ 操作 $nums[0]$ 次，使得 $nums[0..k-1]$ 中的元素都减去 $nums[0]$ ，这样 $nums[0]$ 就变成了 $0$ 。

对一段连续的元素同时进行加减操作，我们可以使用差分数组来维护这些操作，我们用 $d[i]$ 表示差分数组，对差分数组求前缀和，就可以得到每个位置的数值的变化量。

因此，我们遍历 $nums$ ，对于每个元素 $nums[i]$ ，当前位置的变化量 $s = \sum_{j=0}^{i} d[j]$ ，我们将 $nums[i]$ 加上 $s$ ，就得到了当前 $nums[i]$ 的实际值。

如果 $nums[i] = 0$ ，那么无须进行操作，直接跳过。
如果 $nums[i]=0$ ，或者 $i + k \gt n$ ，说明经过前面的操作， $nums[i]$ 已经变成了负数，或者 $nums[i..i+k-1]$ 越界，那么无法使得 $nums$ 中的所有元素都等于 $0$ ，返回 false。否则，我们需要将 $[i..i+k-1]$ 这段区间的所有元素都减去 $nums[i]$ ，因此我们将 $s$ 减去 $nums[i]$ ，并将 $d[i+k]$ 加上 $nums[i]$ 。
继续遍历下一个元素。

遍历结束，说明可以使得 $nums$ 中的所有元素都等于 $0$ ，返回 true。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        d = [0] * (n + 1)
        s = 0
        for i, x in enumerate(nums):
            s += d[i]
            x += s
            if x == 0:
                continue
            if x < 0 or i + k > n:
                return False
            s -= x
            d[i + k] += x
        return True

speed

复杂度分析

指标	值
时间	complexity is O(n) due to single-pass prefix sum updates, and space complexity is O(n) for the difference array storing operation effects. The greedy subarray reduction avoids nested loops.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask for an O(n) solution using a prefix sum or difference array to avoid TLE on large arrays.
question_mark
Probe how the order of applying operations affects the ability to reach zero, especially at boundaries.
question_mark
Check if candidates handle cases where k equals array length or when elements exceed available operations.

warning

常见陷阱

外企场景

error
Failing to account for cumulative operations when reducing elements leads to over- or under-subtracting.
error
Attempting to brute-force every subarray results in O(n*k) time and may time out on large inputs.
error
Ignoring boundary elements beyond n-k+1 can cause incorrect false negatives even when zeroing is possible.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to maximize operations applied before reaching zero, focusing on order selection.
arrow_right_alt
Allow negative numbers in nums and track net operations needed using a signed prefix sum array.
arrow_right_alt
Change k dynamically per operation and determine feasibility using a sliding window difference approach.

help

常见问题

外企场景

继续练习

#2731 移动机器人 #2845 统计趣味子数组的数目 #2848 与车相交的点