[每日 LeetCode] 985. Sum of Even Numbers After Queries

Description:

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 addval to A[index].  Then, the answer to the i-th query is the sum of the even values of A.

(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.
​

思路：本题大意是：给出原始的数组，然后给出了一串查询步骤，每次查询的时候，都会在指定位置 queries[i]加上 queries[i][0]，在每次操作完毕之后，把所有数值是偶数的数字求和保存起来。求经过一系列的查询之后，返回生成的偶数之和序列。

最开始想到的是采用暴力求解方法，依次遍历 queries 数组，每次查询之后都去遍历一次，计算偶数之和，保存起来。可惜代码超时了。

有一个比较巧妙的方法，需要找规律发现。即可以先求出原始数组所有偶数之和，然后对于每次查询的，判断如果 A[index]是偶数，那么就把这个值减去，然后把查询要添加的数值 val 加到 A[index]上。如果加完的结果是偶数的话，需要把该结果加到 sum 上。

C++ 代码（暴力求解，超时未通过）

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
        vector<int> B; //Output array B
        int index,val;
        int sum;
        for(int i=0;i<A.size();i++) {
            index=queries[i][1];
            val=queries[i][0];
            A.at(index)+=val; 
            sum=0;
            for(int j=0;j<A.size();j++) {
                if(A[j]%2==0) {
                    sum+=A[j];
                }
            }
            B.push_back(sum);
        }
        return B;
    }
};
​

C++ 代码

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
        int s = 0, v, p;
        vector<int> r(queries.size(), 0);
        for (auto a : A) if ((a&1) == 0) s += a;
        for (size_t i=0; i<queries.size(); ++i)
        {
            v = queries[i][0];
            p = queries[i][1];
            if ((A[p]&1) == 0)
            {
                s -= A[p];
            }
            A[p] += v;
            if ((A[p]&1) == 0) s += A[p];
            r[i] = s;
        }
        return r;
    }
};
​

运行时间：164ms

运行内存：28.1M