查询后的偶数和
难度:
标签:
题目描述
代码结果
运行时间: 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中初始没有偶数元素,算法是否仍然能正确处理偶数和的计算?
▷🦆
对于更新数组元素时的边界情况,如原先元素和修改值均为负数,题解中的算法是否已经足够处理这样的情况?例如,如果原先元素为-2,修改值为-3,更新后的元素为-5。
▷🦆
题解中关于偶数和的更新,是否考虑了所有可能导致偶数变奇数,或奇数变偶数的场景?例如,一个偶数加上一个偶数仍然是偶数,但加上一个奇数则变为奇数。
▷🦆
在更新数组元素和重新计算偶数和时,是否有更高效的方法来避免重复计算,尤其是在连续多次查询中对同一个索引进行修改的情况?
▷