這是悅樂書的第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+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。
以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)