描述
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:
1 | Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]] |
Note:
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
1 <= queries.length <= 10000
-10000 <= queries[i][0] <= 10000
0 <= queries[i][1] < A.length
分析
最简单的方式是直接按照题意两次循环,时间复杂度是 $O(Q*N)$,$Q$ 是 $queries$ 的长度,$N$ 是 $A$ 的长度。空间复杂度是 $O(Q)$。该方法用 Java 实现
Solution 里有一个讨巧的方式,先把 A 的偶数和都计算出来,记为 S,时间复杂度是 $O(N)$,接着遍历 queries,首先判断 A[index] 是否为偶数,如果为偶数,S 要减去 A[index],因为不能把 A[index] 纳入和的计算,接着再根据 A[index] + val 计算真正的和。该方法用 Python 实现。
解决方案1(Python)
1 | class Solution(object): |
解决方案1(Java)
1 | class Solution { |