【差分数组】2772. 使数组中的所有元素都等于零

本文涉及知识点

差分数组

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

给你一个下标从 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⁶

差分数组

操作顺序不影响结果，我们按下标的升序操作。
i1 为第一个不为0的nums[i]的下标。选择的子数组，不能包括nums[0…i-1]的任意元素，否则此元素变成负数。那么此子序列只能是[i1,i1+i)
for i = 0 : n-1
如果nums[i]大于0
$$\{\begin{array}{llc}nums[i...i+k-1]都减1& & i+k<=n\\ returnfalse& & other\end{array}$$

代码

核心代码

class Solution {
public:
	bool checkArray(vector<int>& nums, int k) {
		const int N = nums.size();
		vector<long long> vDiff(N + 1);
		long long sum = 0;
		for (int i = 0; i < N; i++) {
			sum += vDiff[i];
			const long long llSub = sum + nums[i];
			if (llSub < 0) { return false; }
			if (0 == llSub) { continue; }
			if (i + k > N) { return false; }
			vDiff[i] -= llSub;
			sum -= llSub;
			vDiff[i + k] += llSub;
		}
		return true;
	}
};

单元测试

namespace UnitTest
{
	vector<int> nums;
	int k;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{
			nums = { 2, 2, 3, 1, 1, 0 }, k = 3;
			auto res = Solution().checkArray(nums, k);
			AssertEx( true, res);
		}
		TEST_METHOD(TestMethod1)
		{
			nums = { 1,3,1,1 }, k = 2;
			auto res = Solution().checkArray(nums, k);
			AssertEx(false, res);
		}
	};
}

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。