这是悦乐书的第370次更新，第398篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第232题（顺位题号是985）。有一个整数数组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]。
在向A[0]加1后，数组为[2,2,3,4]，偶数值之和为2 + 2 + 4 = 8。
在向A[1]加-3后，数组为[2，-1,3,4]，偶数值之和为2 + 4 = 6。
在向A[0]加上-4后，数组为[-2，-1,3,4]，偶数值之和为-2 + 4 = 2。
在向A[3]加2后，数组为[-2，-1,3,6]，偶数值之和为-2 + 6 = 4。
注意：
-
1 <= A.length <= 10000
-
-10000 <= A[i] <= 10000
-
1 <= queries.length <= 10000
-
-10000 <= queries[i][0] <= 10000
-
0 <= queries[i][1] <A.length
02 第一种解法
直接翻译题目，找出queries中对应的索引和val，改变A中对应元素的的值，接着利用循环求A中偶数元素的总和，赋值给结果数组result。
此解法的时间复杂度为O(M*N)，M为queries的长度，N为A的长度，空间复杂度为O(M)，M为queries的长度。
public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
int len = queries.length;
int[] result = new int[len];
for (int i=0; i<len; i++) {
A[queries[i][1]] += queries[i][0];
result[i] = evenSum(A);
}
return result;
}
public int evenSum(int[] A){
int sum = 0;
for (int num : A) {
if (num%2==0) {
sum += num;
}
}
return sum;
}
03 第二种解法
第一种解法的时间复杂度太高了，还可以再优化下。
结果数组中的值，后一位是在前一位的基础上产生的，主要判断A中的当前位元素值、queries中的值的奇偶性。拿题目给的示例来看，在第二次操作后，A变成了[2，-1,3,4]，将第一次操作后的数组A=[2,2,3,4]中的第二个元素变成了-1，而第一次操作的偶数元素和是8，现在第二个元素变成了奇数，就需要将第一次加的2给减掉，所以第二次操作后的偶数和变成了8-2=6，剩下的几步操作都可以这样理解。
因此，我们就需要判断当前要操作的的A[i]的奇偶和queries[i][0]的奇偶，可以分为四种情况：
第一种情况：queries[i][0]为偶数、A[i]也为偶数，即前一次的求和中有A[i]，只需加上queries[i][0]的值即可，即sum = sum + queries[i][0]。
第二种情况：queries[i][0]为偶数、A[i]为奇数，即前一次的求和中没有A[i]，并且A[i]加上queries[i][0]后也是奇数，所以不用更新sum的值。
第三种情况：queries[i][0]为奇数、A[i]为偶数，即前一次的求和中有A[i]，现在A[i]加上queries[i][0]后变成了奇数，需要将前一次求和中的A[i]减掉，即sum = sum - A[i]。
第四种情况：queries[i][0]为奇数、A[i]也为奇数，即前一次的求和中没有A[i]，但是A[i]加上queries[i][0]后变成了偶数，需要把这个新的偶数加到sum上，即sum = sum + queries[i][0] + A[i]。
在计算完sum的值后，将sum赋值给新数组对应位置元素，将ueries[i][0] + A[i]的值赋值给A[i]，最后返回结果数组。
此解法的时间复杂度为O(M)，M为queries的长度，空间复杂度为O(M)，M为queries的长度。
public int[] sumEvenAfterQueries2(int[] A, int[][] queries) {
int sum = 0, i = 0;
for (int num : A) {
if (num%2 == 0) {
sum += num;
}
}
int[] result = new int[queries.length];
for (int[] arr : queries) {
int curval = arr[0];
int preval = A[arr[1]];
// 做奇偶判断
if (curval%2 == 0) {
if (preval%2 == 0) {
sum = sum + curval;
}
} else {
if (preval%2 == 0) {
sum = sum - preval;
} else {
sum = sum + curval + preval;
}
}
A[arr[1]] += curval;
result[i++] = sum;
}
return result;
}
04小结
算法专题目前已连续日更超过七个月，算法题文章238+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论