力扣热题——零数组变换 |

目录

题目链接：3355. 零数组变换 I - 力扣（LeetCode）

题目描述

解法一：前缀和

解决思路

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

解法二：

Java写法：

C++写法：

运行时间

时间复杂度和空间复杂度

总结

---

题目链接：3355. 零数组变换 I - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

给定一个长度为 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：
  • 选择下标子集 [0, 2] 并将这些下标处的值减 1。
  • 数组将变为 [0, 0, 0]，这是一个零数组。

示例 2：

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

输出： false

解释：

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

提示：

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

---

解法一：前缀和

解决思路

该问题的核心在于判断每个元素能否通过查询操作被足够次数地减1，最终变为0。关键在于​​每个元素被覆盖的查询次数必须至少等于其初始值​​。具体思路如下：

1. ​​差分数组统计覆盖次数​​
   使用差分数组高效统计每个元素被查询区间覆盖的次数。对于每个查询区间 [l, r]，在差分数组 diff[l] 处加1，diff[r+1] 处减1。通过前缀和计算每个位置的实际覆盖次数。

2. ​​验证覆盖次数是否足够​​
   遍历每个元素，若其被覆盖的次数小于初始值，则无法通过操作归零，返回 false；否则返回 true。

Java写法：

public class Solution {public boolean isZeroArray(int[] nums, int[][] queries) {int n = nums.length;int[] diff = new int[n + 1];// 构建差分数组for (int[] q : queries) {int l = q[0], r = q[1];diff[l]++;if (r + 1 < n) { // 防止越界diff[r + 1]--;}}// 计算前缀和并验证int current = 0;for (int i = 0; i < n; i++) {current += diff[i];if (current < nums[i]) {return false;}}return true;}
}

C++写法：

#include <vector>
using namespace std;class Solution {
public:bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();vector<int> diff(n + 1, 0);// 构建差分数组for (auto& q : queries) {int l = q[0], r = q[1];diff[l]++;if (r + 1 <= n) { // 确保不越界diff[r + 1]--;}}// 计算前缀和并验证int current = 0;for (int i = 0; i < n; ++i) {current += diff[i];if (current < nums[i]) {return false;}}return true;}
};

运行时间

时间复杂度和空间复杂度

• ​​时间复杂度​​：O(n + q)，其中 n 为数组长度，q 为查询数量。差分数组构建和前缀和计算各需线性时间。
• ​​空间复杂度​​：O(n)，差分数组额外占用 n+1 空间。

---

---

---

总结

        本文介绍了力扣题目“零数组变换I”的解法，核心在于判断数组能否通过一系列查询操作归零。解法一采用前缀和与差分数组技术，高效统计每个元素被查询区间覆盖的次数，并验证是否足够使其归零。文章提供了Java和C++的实现代码，并分析了时间复杂度和空间复杂度。时间复杂度为O(n+q)，空间复杂度为O(n)，适用于大规模数据处理。通过这种方法，能够快速判断数组是否可以通过给定查询操作转换为零数组。