leetcode
leetcode 901 ~ 950
查询后的偶数和

查询后的偶数和

难度:

标签:

题目描述

代码结果

运行时间: 53 ms, 内存: 20.8 MB


/*
 * Problem Statement:
 * Given an integer array A and a query array queries.
 * For the i-th query, let val = queries[i][0], index = queries[i][1],
 * we add val to A[index]. Then, the answer to the i-th query is the sum of the even values in A.
 * Return an array answer where answer[i] is the answer to the i-th query.
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class Solution {
    public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int sumEven = Arrays.stream(A).filter(x -> x % 2 == 0).sum();
        int[] answer = new int[queries.length];
        
        for (int i = 0; i < queries.length; i++) {
            int val = queries[i][0];
            int index = queries[i][1];
            
            if (A[index] % 2 == 0) sumEven -= A[index];
            
            A[index] += val;
            
            if (A[index] % 2 == 0) sumEven += A[index];
            
            answer[i] = sumEven;
        }
        
        return answer;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] A = {1, 2, 3, 4};
        int[][] queries = {{1, 0}, {-3, 1}, {-4, 0}, {2, 3}};
        System.out.println(Arrays.toString(sol.sumEvenAfterQueries(A, queries))); // Output: [8, 6, 2, 4]
    }
}

解释

方法:

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

时间复杂度:

O(n + m)

空间复杂度:

O(m)

代码细节讲解

🦆
在LeetCode题解中,如果数组A中初始没有偶数元素,算法是否仍然能正确处理偶数和的计算?
是的,算法可以正确处理这种情况。如果数组中初始没有偶数元素,那么初始的偶数和将为0。对于每次查询,算法仍然按照是否将元素改变为偶数来动态更新偶数和,因此即使起始时没有偶数,算法依然能够正确地维护和更新偶数和。
🦆
对于更新数组元素时的边界情况,如原先元素和修改值均为负数,题解中的算法是否已经足够处理这样的情况?例如,如果原先元素为-2,修改值为-3,更新后的元素为-5。
是的,题解中的算法已经足够处理这类情况。算法在处理时不区分元素的正负,只关心元素的奇偶性。无论是正数还是负数,只要它们的奇偶性发生变化,相应的偶数和就会根据算法中的规则进行更新。因此,即使是负数也会被正确处理。
🦆
题解中关于偶数和的更新,是否考虑了所有可能导致偶数变奇数,或奇数变偶数的场景?例如,一个偶数加上一个偶数仍然是偶数,但加上一个奇数则变为奇数。
是的,题解中已经考虑了所有这些场景。算法在每次更新元素后都会检查该元素的新值的奇偶性,并相应地调整偶数和。这包括了从偶数变为奇数和从奇数变为偶数的情况,以及偶数和偶数相加仍然保持偶数的情况。因此,所有导致奇偶性变化的场景都已被涵盖。
🦆
在更新数组元素和重新计算偶数和时,是否有更高效的方法来避免重复计算,尤其是在连续多次查询中对同一个索引进行修改的情况?
题解中已经采用了一种高效的方法来避免重复计算。通过维护一个动态的偶数和并在每次查询时只更新被影响的部分(即当前索引位置的数),算法避免了每次查询后对整个数组重新计算偶数和的需要。这种方法特别适合于频繁修改和查询的情况。然而,对于连续多次查询同一个索引的优化,除非在算法外部对查询进行预处理或合并,算法本身已经是按照每次查询单独处理进行优化的。

相关问题