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.
(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 <= A.length <= 10000-10000 <= A[i] <= 100001 <= queries.length <= 10000-10000 <= queries[i][0] <= 100000 <= 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)
class Solution {
public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
int sum = 0;
int[] result = new int[queries.length];
for(int a: A) {
if((a&1) == 0) {
sum += a;
}
}
for(int i = 0; i < queries.length; ++i) {
int[] query = queries[i];
int index = query[1];
int val = query[0];
if((A[index]&1) == 0) {
if((val&1) == 0) {
sum+= val;
}
else {
sum -= A[index];
}
}
else {
if((val&1) == 1) {
sum += val + A[index];
}
}
A[index] += val;
result[i] = sum;
}
return result;
}
}
看到官方解法才感觉上面的解法笨，好好看题，只有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.
class Solution {
public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
int sum = 0;
int[] result = new int[queries.length];
for(int a: A) {
if((a&1) == 0) {
sum += a;
}
}
for(int i = 0; i < queries.length; ++i) {
int[] query = queries[i];
int index = query[1];
int val = query[0];
if((A[index] & 1) == 0) {
sum -= A[index];
}
A[index] += val;
if((A[index] & 1) == 0) {
sum += A[index];
}
result[i] = sum;
}
return result;
}
}