题目概述
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.
O(N^2)解法
最直接的想法当然就是遍历求和了。但是这样是无法通过测试的。
1 | class Solution3(object): |
死亡凝视
必须要想出复杂度是Nlog(N)
的算法才行。但是问题也很明显,
要想找出所有的s(i,j) for 0 <= i <= j < n and lower <= s(i,j) <= upper
那必须要进行遍历啊,因此时间复杂度必须是N^2
。
啊啊,实在想不出来了。
第二天,既然要求时间复杂度为NlogN
那么就必然不能遍历求出s(i,j)
,但是
题目要求的是求出Num(s(i,j)) for 0 <= i <= j < n and lower <= s(i,j) <= upper
,也就是说给出个数就行,因此确实不一定要给出所有的s(i,j)
。嗯,有点进展了。
第三天,排序算法的复杂度是NlogN
,怎么才能依靠排序算法求出呢。难道对所有的
s(i,j)
进行排序么?这样肯定不行。
能否使用老办法画图呢?这样好观察一下。但是仔细想了想,这是一个三维图。
纸上画不出来。
只好画一个二维图吧。下图是对数组[5,7,8,-2,1]
画的二维表格。格子
中的数字就是s(i,j)
。
我仔细的盯着看。我给这种解决问题的方式,起了
个名字——死亡凝视
。看过The Big Bang
的朋友可能记得Sheldon
和Raj
一起
工作的样子,就是一动不动的看着黑板上的公式,看上一整天。
嘿嘿,你们不要笑啊,我的方式差不多。只不过是盯着表格。这样的表格 其实我画了很多。但是只有这个我看出了规律。
看出来了么,三列带颜色的数字。是不是发现它们有相同的趋势呢? 是的它们有相同的趋势。
如果没有看出来。我再画一个图。看看这三列数字和蓝色数字的关系。
是的。20 - 5 = 15
,18 - 5 = 13
,19 - 5 = 14
。
假如上下区间为[12,18]
,那么对于排序后的第一列[5,12,18,19,20]
,
可以使用二分查找法找出上限的位置是2,下限的位置为1,个数为2。
那么第二列[7,15,13,14]
在[12,18]
的数字的个数为3。
怎么根据第一列排序后的数字求出呢。嗯,很简单。
我们把上下限加上5,变成17, 23
,这样就可以发现[5,12,18,19,20]
找出
个数为3。嗯,哈哈。真是不错。这样子,就不需要求出所有的s(i,j)
了。
但是,别着急,还是有问题,我们需要在计算第二列的个数的之前,把第一列的数字中的5
排除掉。
否则的话,如果区间是[-100,100]
,那么我们就多计算了。
通过的代码
1 | # python3.5 |
总结
排序操作的时间复杂度是O(NlogN)
,而找出每列一列的个数的时间复杂度是O(logN)
因为一共有N列,所以时间复杂度为O(NlogN)
,另外
我们在代码中使用了对List
数据的非尾部的pop
操作,这个操作的时间
复杂度接近O(N)
,严格来说,我们的代码的时间复杂度还是O(N^2)
。如果能够不使用这个操作。
我们的代码速度会更快。
l.pop(pos) # <-- 这里是个接近O(N)的操作