LeetCode 985中等数组 · 哈希
查询后的偶数和 图解题解
这道题到底在问什么
给定整数数组 nums 和查询数组 queries。第 i 次查询有 val 和 index 两个数，把 val 加到 nums[index] 上，然后第 i 次的答案是此刻 nums 里所有偶数值的和。每次查询都会永久改动 nums。返回每次查询的答案数组。
- 输入
- nums=[1,2,3,4], queries=[[1,0],[-3,1],[-4,0],[2,3]]
- 输出
- [8,6,2,4]
- 输入
- nums=[1], queries=[[4,0]]
- 输出
- [0] （1+4=5 是奇数，偶数和为 0）
最优解：一步一步想明白
- 3记住这套「旧偶先减、改值、新偶再加」，下面每次查询都在套它。一个数从偶变奇要减掉，从奇变偶要加上，evenSum 始终是当前真实的偶数和。
- 4开局先把起始数组里的偶数找出来。这里 2 和 4 是偶数（绿色），1 和 3 是奇数。先把它们的和当作 evenSum 的起点。
- 5两个偶数 2 和 4 加起来，evenSum 起始等于 6。注意这一步是查询开始前的准备，还没产生任何答案。接下来每次查询都在这个 6 上增量更新。
- 6第 1 次查询来了，要把 1 加到下标 0（紫色这格，现在是 1）。别急着加，按套路先看这个旧值 1 是奇是偶。
- 7旧值 1 是奇数，它根本没被算进偶数和，所以不用减，evenSum 还是 6。奇数被改不影响已有的偶数和。
- 8现在真正执行加法，下标 0 从 1 变成 2。偶数和先按兵不动，等下看这个新值 2 是不是偶数再决定加不加。
- 9新值 2 是偶数，把它加进偶数和：6 + 2 等于 8。这就是第 1 次查询的答案，记进右边的答案表。
- 10第 2 次查询来了，要把 -3 加到下标 1（紫色这格，现在是 2）。别急着加，按套路先看这个旧值 2 是奇是偶。
- 11旧值 2 是偶数，它现在还待在偶数和里。马上要改它，所以先把它从 evenSum 减出去：8 - 2 等于 6。红色表示这个旧偶数即将离场。
- 12现在真正执行加法，下标 1 从 2 变成 -1。偶数和先按兵不动，等下看这个新值 -1 是不是偶数再决定加不加。
- 13新值 -1 是奇数，进不了偶数和，evenSum 仍是 6。这就是第 2 次查询的答案，照样记进答案表。
- 14第 3 次查询来了，要把 -4 加到下标 0（紫色这格，现在是 2）。别急着加，按套路先看这个旧值 2 是奇是偶。
- 15旧值 2 是偶数，它现在还待在偶数和里。马上要改它，所以先把它从 evenSum 减出去：6 - 2 等于 4。红色表示这个旧偶数即将离场。
- 16现在真正执行加法，下标 0 从 2 变成 -2。偶数和先按兵不动，等下看这个新值 -2 是不是偶数再决定加不加。
- 17新值 -2 是偶数，把它加进偶数和：4 - 2 等于 2。这就是第 3 次查询的答案，记进右边的答案表。
- 18第 4 次查询来了，要把 2 加到下标 3（紫色这格，现在是 4）。别急着加，按套路先看这个旧值 4 是奇是偶。
- 19旧值 4 是偶数，它现在还待在偶数和里。马上要改它，所以先把它从 evenSum 减出去：2 - 4 等于 -2。红色表示这个旧偶数即将离场。
- 20现在真正执行加法，下标 3 从 4 变成 6。偶数和先按兵不动，等下看这个新值 6 是不是偶数再决定加不加。
- 21新值 6 是偶数，把它加进偶数和：-2 + 6 等于 4。这就是第 4 次查询的答案，记进右边的答案表。
- 22四次查询都处理完了。最终数组是 [-2, -1, 3, 6]，绿色的 -2 和 6 是当前仅剩的偶数，它们的和正是最后一次的答案 4。
- 23回头看，我们从头到尾没把整个数组重新加过一遍。每次查询只动一个位置，旧偶先减、新偶再加，evenSum 一路都是对的。这就是增量维护的省力之处。
⚠️ 容易写错的地方
✗ 错：每次查询都把整个数组重新加一遍偶数
✓ 对：维护 evenSum，只动被改的那个位置
重新求和是 O(n·q)，n 和 q 都到一万时会超时
✗ 错：改值前忘了先减旧偶数
✓ 对：旧值是偶数必须先从 evenSum 减掉，再改
不减就把旧偶数重复留在和里，结果偏大
✗ 错：把旧值奇偶和新值奇偶混为一谈
✓ 对：旧偶才减、新偶才加，两个判断各自独立
旧奇不用减、新奇不用加，漏判任一个都会算错
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def sumEvenAfterQueries(
self, nums: List[int], queries: List[List[int]]
) -> List[int]:
s = sum(x for x in nums if x % 2 == 0)
ans = []
for v, i in queries:
if nums[i] % 2 == 0:
s -= nums[i]
nums[i] += v
if nums[i] % 2 == 0:
s += nums[i]
ans.append(s)
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
int s = 0;
for (int x : nums) {
if (x % 2 == 0) {
s += x;
}
}
vector<int> ans;
for (auto& q : queries) {
int v = q[0], i = q[1];
if (nums[i] % 2 == 0) {
s -= nums[i];
}
nums[i] += v;
if (nums[i] % 2 == 0) {
s += nums[i];
}
ans.push_back(s);
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
int s = 0;
for (int x : nums) {
if (x % 2 == 0) {
s += x;
}
}
int m = queries.length;
int[] ans = new int[m];
int k = 0;
for (int[] q : queries) {
int v = q[0], i = q[1];
if (nums[i] % 2 == 0) {
s -= nums[i];
}
nums[i] += v;
if (nums[i] % 2 == 0) {
s += nums[i];
}
ans[k++] = s;
}
return ans;
}
}复杂度
时间
O(n + q)
初始求和扫一遍 O(n)，之后每次查询 O(1)，共 q 次
空间
O(1)
只多用一个 evenSum 变量（不计必须返回的答案数组）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 查询后的偶数和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不能每次查询都重新遍历数组求偶数和？+
那样每次是 O(n)，q 次就是 O(n·q)。当 n、q 都到一万时是一亿次操作，容易超时。增量维护把每次查询压到 O(1)，总共只 O(n+q)。
如果数值范围很大，结果会溢出吗？+
本题范围下偶数和最大约一亿，普通 int 足够；Python 整数天然无界。若范围放大到接近 int 上限，改用 long 或 int64 即可，思路完全不变。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 查询后的偶数和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。