原文链接: https://leetcode-cn.com/problems/sum-of-even-numbers-after-queries
英文原文
You are given an integer array nums and an array queries where queries[i] = [vali, indexi].
For each query i, first, apply nums[indexi] = nums[indexi] + vali, then print the sum of the even values of nums.
Return an integer array answer where answer[i] is the answer to the ith query.
Example 1:
Input: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]] Output: [8,6,2,4] Explanation: At the beginning, the array is [1,2,3,4]. After adding 1 to nums[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8. After adding -3 to nums[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6. After adding -4 to nums[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2. After adding 2 to nums[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.
Example 2:
Input: nums = [1], queries = [[4,0]] Output: [0]
Constraints:
1 <= nums.length <= 104-104 <= nums[i] <= 1041 <= queries.length <= 104-104 <= vali <= 1040 <= indexi < nums.length
中文题目
给出一个整数数组 A 和一个查询数组 queries。
对于第 i 次查询，有 val = queries[i][0], index = queries[i][1]，我们会把 val 加到 A[index] 上。然后，第 i 次查询的答案是 A 中偶数值的和。
（此处给定的 index = queries[i][1] 是从 0 开始的索引，每次查询都会永久修改数组 A。）
返回所有查询的答案。你的答案应当以数组 answer 给出，answer[i] 为第 i 次查询的答案。
示例：
输入：A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]] 输出：[8,6,2,4] 解释： 开始时，数组为 [1,2,3,4]。 将 1 加到 A[0] 上之后，数组为 [2,2,3,4]，偶数值之和为 2 + 2 + 4 = 8。 将 -3 加到 A[1] 上之后，数组为 [2,-1,3,4]，偶数值之和为 2 + 4 = 6。 将 -4 加到 A[0] 上之后，数组为 [-2,-1,3,4]，偶数值之和为 -2 + 4 = 2。 将 2 加到 A[3] 上之后，数组为 [-2,-1,3,6]，偶数值之和为 -2 + 6 = 4。
提示：
1 <= A.length <= 10000-10000 <= A[i] <= 100001 <= queries.length <= 10000-10000 <= queries[i][0] <= 100000 <= queries[i][1] < A.length
通过代码
官方题解
方法：调整数组和
思路与算法
让我们尝试不断调整 S，即每一步操作之后整个数组的偶数和。
我们操作数组中的某一个元素 A[index] 的时候，数组 A 其他位置的元素都应保持不变。如果 A[index] 是偶数，我们就从 S 中减去它，然后计算 A[index] + val 对 S 的影响（如果是偶数则在 S 中加上它）。
这里有一些例子：
如果当前情况为
A = [2,2,2,2,2]、S = 10，并且需要执行A[0] += 4操作：我们应该先令S -= 2，然后令S += 6。最后得到A = [6,2,2,2,2]与S = 14。如果当前情况为
A = [1,2,2,2,2]、S = 8，同时需要执行A[0] += 3操作：我们会跳过第一次更新S的步骤（因为A[0]是奇数），然后令S += 4。 最后得到A = [4,2,2,2,2]与S = 12。如果当前情况为
A = [2,2,2,2,2]、S = 10，同时需要执行A[0] += 1操作：我们先令S -= 2，然后跳过第二次更新S的操作（因为A[0] + 1是奇数）。最后得到A = [3,2,2,2,2]与S = 8。如果当前情况为
A = [1,2,2,2,2]、S = 8，同时需要执行A[0] += 2操作：我们跳过第一次更新S的操作（因为A[0]是奇数），然后再跳过第二次更新S的操作（因为A[0] + 2是奇数）。最后得到A = [3,2,2,2,2]与S = 8。
这些例子充分展现了我们的算法在每一次询问操作之后应该如何调整 S 。
[ZscGXmuD-Java]class Solution { public int[] sumEvenAfterQueries(int[] A, int[][] queries) { int S = 0; for (int x: A) if (x % 2 == 0) S += x; int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; ++i) { int val = queries[i][0], index = queries[i][1]; if (A[index] % 2 == 0) S -= A[index]; A[index] += val; if (A[index] % 2 == 0) S += A[index]; ans[i] = S; } return ans; } }
[ZscGXmuD-Python]class Solution(object): def sumEvenAfterQueries(self, A, queries): S = sum(x for x in A if x % 2 == 0) ans = [] for x, k in queries: if A[k] % 2 == 0: S -= A[k] A[k] += x if A[k] % 2 == 0: S += A[k] ans.append(S) return ans
复杂度分析
时间复杂度：$O(N+Q)$，其中 $N$ 是数组
A的长度， $Q$ 是询问queries的数量。空间复杂度：$O(N+Q)$，事实上我们只使用了 $O(1)$ 的额外空间。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 16536 | 27492 | 60.1% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
