LeetCode 985题：查询后偶数和的低效算法优化咨询

题目说明 #

给定整数数组nums和查询数组queries（每个元素为[valᵢ, indexᵢ]），对每个查询执行两步操作：

1. 将nums[indexᵢ]的值加上valᵢ
2. 返回当前nums中所有偶数的和
   最终返回所有查询结果组成的数组。

示例输入输出 #

# input1: nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
# output1: [8, 6, 2, 4]

# input2: nums = [1], queries = [[4,0]]
# output2: [0]

原代码问题分析 #

你提供的代码每次处理完查询后，都遍历整个数组重新计算偶数和，时间复杂度为O(N*Q)（N为数组长度，Q为查询次数）。当数组长度和查询量都很大时，这种重复遍历会导致超时。

优化方案 #

核心思路是维护一个动态的偶数总和，避免每次都全量计算：

1. 先计算初始状态下数组的偶数总和
2. 针对每个查询，只更新被修改元素对总和的影响：
   • 如果修改前的元素是偶数，先从总和中减去它
   • 执行数值更新操作
   • 如果修改后的元素是偶数，把它加到总和中
   • 记录当前总和到结果数组

优化后的代码 #

class Solution:
    def sumEvenAfterQueries(self, nums: list[int], queries: list[list[int]]) -> list[int]:
        ans = []
        # 计算初始偶数和
        even_sum = sum(num for num in nums if num % 2 == 0)
        
        for val, idx in queries:
            old_num = nums[idx]
            # 移除旧值的贡献（如果是偶数）
            if old_num % 2 == 0:
                even_sum -= old_num
            # 更新数组元素
            nums[idx] += val
            new_num = nums[idx]
            # 添加新值的贡献（如果是偶数）
            if new_num % 2 == 0:
                even_sum += new_num
            # 保存当前结果
            ans.append(even_sum)
        
        return ans

优化效果 #

优化后的时间复杂度为O(N + Q)：初始计算偶数和是O(N)，每个查询仅需O(1)的操作，大幅降低了时间消耗，能处理大数据量输入而不超时。

内容的提问来源于stack exchange，提问作者rockzxm