[leetcode 327]Count of Range Sum 原创解法

题目概述

原题链接

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution3(object):
def countRangeSum(self, nums, lower, upper):
"""
:type nums: List[int]
:type lower: int
:type upper: int
:rtype: int
"""

sums = []

for i in range(len(nums)):
s = 0
for j in range(i, len(nums)):
s += nums[j]
if lower <= s <= upper:
sums.append(s)
return len(sums)

死亡凝视

必须要想出复杂度是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)

327-1

我仔细的盯着看。我给这种解决问题的方式,起了 个名字——死亡凝视。看过The Big Bang的朋友可能记得SheldonRaj一起 工作的样子,就是一动不动的看着黑板上的公式,看上一整天。

327-2

嘿嘿,你们不要笑啊,我的方式差不多。只不过是盯着表格。这样的表格 其实我画了很多。但是只有这个我看出了规律。

327-3

看出来了么,三列带颜色的数字。是不是发现它们有相同的趋势呢? 是的它们有相同的趋势。

如果没有看出来。我再画一个图。看看这三列数字和蓝色数字的关系。

327-4

是的。20 - 5 = 1518 - 5 = 1319 - 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
# python3.5
class Solution4(object):
def countRangeSum(self, nums, lower, upper):
"""
思路:对 list0 = [s(0,j) for j in (0,n)]先进行排序。
list1 = [s(1,j) for j in (1,n)],可以由 list0生成。

:type nums: List[int]
:type lower: int
:type upper: int
:rtype: int
"""
if not nums:
return 0
else:
result = 0
n = len(nums)
l = []
l2 = []
sum = 0
for i in range(0, n):
sum += nums[i]
l.append((sum, i))
l2.append((sum, i))
l.sort()
for i in range(0, n):
if i > 0:
lower += nums[i - 1]
upper += nums[i - 1]
lower_pos = self.find_lower(l, lower)
upper_pos = self.find_uppper(l, upper)
if lower_pos is not None and upper_pos is not None:
result += upper_pos - lower_pos + 1
pos = self.find_lower(l, l2[i][0])
l.pop(pos) # <-- 这里是个接近O(N)的操作

return result

def find(self, nums, target):
n = len(nums)

start = 0
end = n
mid = n // 2
new_mid = None

while 0 <= mid < n:
if nums[mid][0] == target:
break
elif nums[mid][0] < target and mid + 1 < n and nums[mid + 1][0] > target:
break
elif nums[mid][0] < target:
start = mid
new_mid = (start + end) // 2
elif nums[mid][0] > target:
end = mid
new_mid = (start + end) // 2
if new_mid == mid:
mid += 1
else:
mid = new_mid

return mid if nums[mid][0] == target else mid + 1

def find_lower(self, nums, lower):
n = len(nums)
if lower > nums[n - 1][0]:
return None
elif lower < nums[0][0]:
return 0
else:
mid = self.find(nums, lower)
while mid - 1 >= 0 and nums[mid - 1][0] == lower:
mid -= 1
return mid

def find_uppper(self, nums, upper):
n = len(nums)
if upper > nums[n - 1][0]:
return n - 1
elif upper < nums[0][0]:
return None
else:
mid = self.find(nums, upper)
while mid < n - 1 and nums[mid + 1][0] == upper:
mid += 1
return mid if nums[mid][0] == upper else mid - 1

总结

排序操作的时间复杂度是O(NlogN),而找出每列一列的个数的时间复杂度是O(logN) 因为一共有N列,所以时间复杂度为O(NlogN),另外 我们在代码中使用了对List数据的非尾部的pop操作,这个操作的时间 复杂度接近O(N),严格来说,我们的代码的时间复杂度还是O(N^2)。如果能够不使用这个操作。 我们的代码速度会更快。

l.pop(pos) # <-- 这里是个接近O(N)的操作