3355.零数组变换 I：差分数组

【LetMeFly】3355.零数组变换 I：差分数组

力扣题目链接：https://leetcode.cn/problems/zero-array-transformation-i/

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。

对于每个查询 queries[i]：

  • 在 nums 的下标范围 [li, ri] 内选择一个下标 子集。
  • 将选中的每个下标对应的元素值减 1。

零数组 是指所有元素都等于 0 的数组。

如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。

 

示例 1：

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

输出： true

解释：

  • 对于 i = 0： 
    <ul>
	<li>选择下标子集 <code>[0, 2]</code> 并将这些下标处的值减 1。</li>
	<li>数组将变为 <code>[0, 0, 0]</code>，这是一个零数组。</li>
</ul>
</li>

示例 2：

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

输出： false

解释：

  • 对于 i = 0：  
    <ul>
	<li>选择下标子集 <code>[1, 2, 3]</code> 并将这些下标处的值减 1。</li>
	<li>数组将变为 <code>[4, 2, 1, 0]</code>。</li>
</ul>
</li>
<li><strong>对于 i = 1：</strong>
<ul>
	<li>选择下标子集 <code>[0, 1, 2]</code> 并将这些下标处的值减 1。</li>
	<li>数组将变为 <code>[3, 1, 0, 0]</code>，这不是一个零数组。</li>
</ul>
</li>

 

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= li <= ri < nums.length

解题方法：差分数组

创建一个$op$数组，假设某个query是从$0$到$3$，那么就将$op[0]$到$op[3]$都加一(代表下标$0$到$3$都可以被操作一次)，其中$op[i]$代表$nums[i]$一共被操作多少次。

创建一个$diff$数组，其中$diff[i]$代表数组$op[i]-op[i-1]$的差值。

假设想让$op[l]$到$op[r]$都加一，那么其实只需要$diff[l]$加一$diff[r + 1]$减一，$op$数组直接扔了都行。

执行完所有操作(更新好diff数组)后，$\sum_0^i diff[i]$即为$op[i]$的值。

如果存在任何一个$i$的$nums[i]\gt op[i]$，就说明$nums[i]$无法减为$0$，返回false。

  • 时间复杂度$O(len(queries)+len(nums))$
  • 空间复杂度$O(len(nums))$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * @Author: LetMeFly
 * @Date: 2025-05-21 23:06:35
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-21 23:14:28
 */
class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> diff(nums.size() + 1);
        for (vector<int>& q : queries) {
            diff[q[0]]++;
            diff[q[1] + 1]--;
        }
        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            cnt += diff[i];
            if (nums[i] > cnt) {
                return false;
            }
        }
        return true;
    }
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
Author: LetMeFly
Date: 2025-05-21 23:06:35
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-21 23:19:48
'''
from typing import List

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        diff = [0] * (len(nums) + 1)
        for l, r in queries:
            diff[l] += 1
            diff[r + 1] -= 1
        cnt = 0
        for i in range(len(nums)):
            cnt += diff[i]
            if nums[i] > cnt:
                return False
        return True

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * @Author: LetMeFly
 * @Date: 2025-05-21 23:06:35
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-21 23:20:50
 */
class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int[] diff = new int[nums.length + 1];
        for (int[] q : queries) {
            diff[q[0]]++;
            diff[q[1] + 1]--;
        }
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            cnt += diff[i];
            if (nums[i] > cnt) {
                return false;
            }
        }
        return true;
    }
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
 * @Author: LetMeFly
 * @Date: 2025-05-21 23:06:35
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-05-21 23:23:00
 */
package main

func isZeroArray(nums []int, queries [][]int) bool {
    diff := make([]int, len(nums) + 1)
    for _, q := range queries {
        diff[q[0]]++
        diff[q[1] + 1]--
    }
    cnt := 0
    for i := 0; i < len(nums); i++ {
        cnt += diff[i]
        if nums[i] > cnt {
            return false
        }
    }
    return true
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源