查询后的偶数和

标签: 数组 模拟

难度: Medium

给出一个整数数组 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. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. 1 <= queries.length <= 10000
  4. -10000 <= queries[i][0] <= 10000
  5. 0 <= queries[i][1] < A.length

Submission

运行时间: 53 ms

内存: 20.8 MB

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        sums = sum(n for n in nums if n % 2 == 0)
        res = []
        for x, i in queries:
            if nums[i] % 2 == 0:
                sums -= nums[i]
            
            nums[i] += x
            if nums[i] % 2 == 0:
                sums += nums[i]
            res.append(sums)
        return res

Explain

该题解采用的主要思路是先计算数组中所有偶数的和，然后对于每个查询，根据查询的内容更新数组和偶数和。更新步骤包括：1) 检查被修改的元素是否为偶数，如果是，则从当前偶数和中减去该元素；2) 应用查询，即在指定索引处加上查询值；3) 再次检查更新后的元素是否为偶数，如果是，则将其加回偶数和；4) 将当前的偶数和存储为该查询的结果。通过这种方式，我们可以有效地在每次查询后直接计算出偶数和，而无需每次都重新遍历整个数组。

时间复杂度: O(n + m)

空间复杂度: O(m)

class Solution:
    def sumEvenAfterQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        # 计算初始时偶数的总和
        sums = sum(n for n in nums if n % 2 == 0)
        res = []
        for x, i in queries:
            # 如果当前索引的数是偶数，先从sums中减去这个数
            if nums[i] % 2 == 0:
                sums -= nums[i]
            
            # 对当前索引的数进行更新
            nums[i] += x
            # 如果更新后的数是偶数，将其加到sums中
            if nums[i] % 2 == 0:
                sums += nums[i]
            # 将当前得到的偶数和添加到结果列表中
            res.append(sums)
        return res

Explore

是的，算法可以正确处理这种情况。如果数组中初始没有偶数元素，那么初始的偶数和将为0。对于每次查询，算法仍然按照是否将元素改变为偶数来动态更新偶数和，因此即使起始时没有偶数，算法依然能够正确地维护和更新偶数和。

是的，题解中的算法已经足够处理这类情况。算法在处理时不区分元素的正负，只关心元素的奇偶性。无论是正数还是负数，只要它们的奇偶性发生变化，相应的偶数和就会根据算法中的规则进行更新。因此，即使是负数也会被正确处理。

是的，题解中已经考虑了所有这些场景。算法在每次更新元素后都会检查该元素的新值的奇偶性，并相应地调整偶数和。这包括了从偶数变为奇数和从奇数变为偶数的情况，以及偶数和偶数相加仍然保持偶数的情况。因此，所有导致奇偶性变化的场景都已被涵盖。

题解中已经采用了一种高效的方法来避免重复计算。通过维护一个动态的偶数和并在每次查询时只更新被影响的部分（即当前索引位置的数），算法避免了每次查询后对整个数组重新计算偶数和的需要。这种方法特别适合于频繁修改和查询的情况。然而，对于连续多次查询同一个索引的优化，除非在算法外部对查询进行预处理或合并，算法本身已经是按照每次查询单独处理进行优化的。