We have an array A of integers, and an array queries of queries.

For the i-th query 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 of A.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries.  Your answer array should have answer[i] as the answer to the i-th query.

 

Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]] Output: [8,6,2,4] Explanation:  At the beginning, the array is [1,2,3,4]. After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8. After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6. After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2. After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

 

Note:

  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
 Idea 1. To avoid go through the array A every time a query element is visited, saving the even sum is a good idea, plus taking the observation: even + even -> even odd + odd -> even even + odd -> odd Time complexity: O(N + Q), N = A.length, Q = queries.length Space complexity: O(1)  
 1 class Solution {
 2     public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
 3         int sum = 0;
 4         int[] result = new int[queries.length];
 5         for(int a: A) {
 6             if((a&1) == 0) {
 7                 sum += a;
 8             }
 9         }
10         
11         for(int i = 0; i < queries.length; ++i) {
12             int[] query = queries[i];
13             int index = query[1];
14             int val = query[0];
15             if((A[index]&1) == 0) {
16                 if((val&1) == 0) {
17                     sum+= val;
18                 }
19                 else {
20                     sum -= A[index];
21                 }
22             }
23             else {
24                 if((val&1) == 1) {
25                     sum += val + A[index];
26                 }
27             }
28             A[index] += val;
29             result[i] = sum;
30         }
31         
32         return result;
33     }
34 }

看到官方解法才感觉上面的解法笨，好好看题，只有even value matters, new value replaced by one one, if old one is even, deduct it, if new value is even, add it, simple as it is, no need to check all the combinations of even/odd cases.

 1 class Solution {
 2     public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
 3         int sum = 0;
 4         int[] result = new int[queries.length];
 5         for(int a: A) {
 6             if((a&1) == 0) {
 7                 sum += a;
 8             }
 9         }
10         
11         for(int i = 0; i < queries.length; ++i) {
12             int[] query = queries[i];
13             int index = query[1];
14             int val = query[0];
15         
16             if((A[index] & 1) == 0) {
17                 sum -= A[index];
18             }
19             A[index] += val;
20             if((A[index] & 1) == 0) {
21                 sum += A[index];
22             }
23             result[i] = sum;
24         }
25         
26         return result;
27     }
28 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄