Medium

题目描述

给你一个整数数组 nums 和一个查询数组 queries，其中 queries[i] = [val_i, index_i]。

对于每个查询 i，首先，向 nums[index_i] 添加 val_i，即执行 nums[index_i] = nums[index_i] + val_i，然后打印 nums 中偶数值的和。

返回一个整数数组 answer，其中 answer[i] 是第 i 个查询的答案。

示例 1：

输入：nums = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
输出：[8,6,2,4]
解释：开始时，数组为 [1,2,3,4]。
将 1 加到 nums[0] 上之后，数组为 [2,2,3,4]，偶数值之和为 2 + 2 + 4 = 8。
将 -3 加到 nums[1] 上之后，数组为 [2,-1,3,4]，偶数值之和为 2 + 4 = 6。
将 -4 加到 nums[0] 上之后，数组为 [-2,-1,3,4]，偶数值之和为 -2 + 4 = 2。
将 2 加到 nums[3] 上之后，数组为 [-2,-1,3,6]，偶数值之和为 -2 + 6 = 4。

示例 2：

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

提示：

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • 1 <= queries.length <= 10^4
  • -10^4 <= val_i <= 10^4
  • 0 <= index_i < nums.length

解题思路

这道题目要求我们在每次查询后计算数组中偶数的和。我们可以采用两种方法来解决：

方法一：朴素解法 对于每个查询，更新对应位置的值，然后重新计算整个数组中偶数的和。这种方法简单直接，但时间复杂度较高。

方法二：优化解法（推荐） 我们可以先计算初始数组中所有偶数的和，然后对于每个查询操作，只需要根据更新前后的值来调整这个偶数和。具体步骤如下：

  1. 预先计算数组中所有偶数的和
  2. 对于每个查询 [val, index]：
    • 记录当前 nums[index] 的值为 old_val
    • 如果 old_val 是偶数，从总和中减去它
    • 更新 nums[index] += val，得到新值 new_val
    • 如果 new_val 是偶数，将其加到总和中
    • 将当前的偶数和加入结果数组

这种方法避免了每次查询都要重新计算整个数组的和，大大提升了效率。

代码实现

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int evenSum = 0;
        for (int num : nums) {
            if (num % 2 == 0) {
                evenSum += num;
            }
        }
        
        vector<int> result;
        for (auto& query : queries) {
            int val = query[0];
            int index = query[1];
            
            int oldVal = nums[index];
            if (oldVal % 2 == 0) {
                evenSum -= oldVal;
            }
            
            nums[index] += val;
            int newVal = nums[index];
            if (newVal % 2 == 0) {
                evenSum += newVal;
            }
            
            result.push_back(evenSum);
        }
        
        return result;
    }
};

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        even_sum = sum(num for num in nums if num % 2 == 0)
        
        result = []
        for val, index in queries:
            old_val = nums[index]
            if old_val % 2 == 0:
                even_sum -= old_val
            
            nums[index] += val
            new_val = nums[index]
            if new_val % 2 == 0:
                even_sum += new_val
            
            result.append(even_sum)
        
        return result

public class Solution {
    public int[] SumEvenAfterQueries(int[] nums, int[][] queries) {
        int evenSum = 0;
        foreach (int num in nums) {
            if (num % 2 == 0) {
                evenSum += num;
            }
        }
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int val = queries[i][0];
            int index = queries[i][1];
            
            int oldVal = nums[index];
            if (oldVal % 2 == 0) {
                evenSum -= oldVal;
            }
            
            nums[index] += val;
            int newVal = nums[index];
            if (newVal % 2 == 0) {
                evenSum += newVal;
            }
            
            result[i] = evenSum;
        }
        
        return result;
    }
}

var sumEvenAfterQueries = function(nums, queries) {
    let evenSum = nums.reduce((sum, num) => num % 2 === 0 ? sum + num : sum, 0);
    let result = [];
    
    for (let [val, index] of queries) {
        let oldVal = nums[index];
        let newVal = oldVal + val;
        
        if (oldVal % 2 === 0) {
            evenSum -= oldVal;
        }
        
        nums[index] = newVal;
        
        if (newVal % 2 === 0) {
            evenSum += newVal;
        }
        
        result.push(evenSum);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型朴素解法优化解法
时间复杂度O(n × q)O(n + q)
空间复杂度O(1)O(1)

其中 n 是数组长度，q 是查询次数。优化解法通过维护偶数和避免了重复计算，将时间复杂度从 O(n × q) 降低到 O(n + q)。