最近在leetcode上刷算法题,发现了一道比较有意思的题目,虽然不难,但要想尽可能的降低时间复杂度达到最优解,还是要有点技巧的,我们来看看。

题干

sum-of-even-numbers-after-queries。这道题的意思是说,给定一个包含一系列数字的数组A,和一个queries数组,对于queries[i],设定val=queries[i][0]index=queries[i][1],使得A[index]+=val,求ans数组,使得ans[i]为经过queries[i]之后的A数组所有偶数数字之和。

初步模拟

初看完题目,我马上想到这不就是个简单的模拟题吗?照着题干的意思写不就行了,再一看数据范围不超过10000,嗯,O(n^2)先试试看,应该不会超时。于是很快的就把代码写出来了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {number[]} A
* @param {number[][]} queries
* @return {number[]}
*/
var sumEvenAfterQueries = function(A, queries) {
var ans = [], val = null, index = 0, evenSum = 0;
for (var i = 0, l = queries.length; i < l; i++) {
val = queries[i][0];
index = queries[i][1];
A[index] += val;
evenSum = 0;
for (var j = 0, l2 = A.length; j < l2; j++) {
if (A[j] % 2 === 0) {
evenSum += A[j];
}
}
ans.push(evenSum);
}
return ans;
};

写完提交,成功!emmmm,很简单嘛,下一题…..

等等,这时间好像有点多啊,8216ms,差一点就超时了。不行,肯定有什么更简便的方法。

数学妙用

在经过别人的答案启发后,我突然发现原来利用数学的知识这道题可以这么简单!话不多说,我们来看代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var sumEvenAfterQueries = function(A, queries) {
var ans = [], val = null, index = 0, tmpSum = 0, evenSum = 0;
evenSum = A.reduce((p, n) => {
return n % 2 === 0 ? p + n : p;
}, 0);

queries.forEach((query) => {
val = query[0];
index = query[1];
tmpSum = A[index] + val;
tmpSum % 2 === 0 ?
(A[index] % 2 === 0 ? evenSum += val : evenSum += tmpSum)
: (A[index] % 2 === 0 ? evenSum -= A[index] : null)
A[index] = tmpSum;
ans.push(evenSum);
})
return ans;
};

写完一提交
leetcode-result
居然只用了这么短时间!!!复杂度也只有O(n),怎么做到的呢?

我们来分析分析:

1
2
3
evenSum = A.reduce((p, n) => {
return n % 2 === 0 ? p + n : p;
}, 0);

首先我们先把原始数组所有偶数数字加起来,为了方便之后直接在上面加减。

1
2
3
4
5
tmpSum % 2 === 0 ?
(A[index] % 2 === 0 ? evenSum += val : evenSum += tmpSum)
: (A[index] % 2 === 0 ? evenSum -= A[index] : null)
A[index] = tmpSum;
ans.push(evenSum);

接着这段最关键的代码,我们对每次加完后的数字tmpSum进行判断,如果是偶数的话,分两种情况:A[index]是偶数,则代表之前的evenSum已经把A[index]加进去了,所以我们只用加上新的val,反之我们把A[index]val都给加上;如果是奇数,我们则需要判断之前的A[index]是不是偶数,是的话需要把它给减去。

经过这样的处理最后得到的就是每一轮所有偶数的和,最后完美的解决了问题,时间复杂度也只有O(n)。

总结

虽然这道题很简单,但我还是想记录下来,因为它代表了一种思维方法,以后做算法题或者写业务代码时都应该多问问自己,还有没有最优解?还能不能继续优化?我们很多时候都是做完结果对了就万事大吉,等到问题出现的时候才去想怎么去解决。而大多时候的问题都是有更好的解决办法的,不怕你做不到,就怕你想不到。平时做事时多拓宽自己的思路,我们在真正遇到问题的时候才不会害怕。