迪子员工爆料:老员工的学历和能力都堪忧啊，三本野鸡大学毕业，还管理一堆985，211硕士，华为腾讯的下属。。
虎哥约 4 分钟最近刷到一条猛料：迪子员工爆料，说他们公司那些老员工不仅学历堪忧，还是三本毕业，居然还能管理一堆985、211的高材生！甚至还有从华为、腾讯挖过来的下属。
网友直接炸锅了：这不合理啊，凭什么呀？
算法题：区间和的个数
题目背景
nums 和两个整数 lower 和 upper，找到数组中所有区间和（也就是从数组中某一段连续子数组的和）的个数，要求区间和在 [lower, upper] 之间。nums = [-2, 5, -1]，lower = -2，upper = 2。结果是 3，因为满足条件的区间有：[-2][-2, 5, -1][5, -1]
解法优化
用前缀和 + 二分查找
[lower, upper] 之间。这里我们可以用 二分查找 或者 归并排序，两个方法都很有意思。归并排序解法
def countRangeSum(nums, lower, upper):
def merge_sort(start, end):
if start >= end:
return 0
mid = (start + end) // 2
count = merge_sort(start, mid) + merge_sort(mid + 1, end)# 统计区间和的个数
j, k, t = mid + 1, mid + 1, mid + 1
temp = []
for i in range(start, mid + 1):
while k <= end and prefix_sum[k] - prefix_sum[i] < lower:
k += 1
while j <= end and prefix_sum[j] - prefix_sum[i] <= upper:
j += 1
count += j - k# 归并过程
while t <= end and prefix_sum[t] < prefix_sum[i]:
temp.append(prefix_sum[t])
t += 1
temp.append(prefix_sum[i])
temp.extend(prefix_sum[t:end + 1])
prefix_sum[start:end + 1] = tempreturn count
# 计算前缀和
prefix_sum = [0]
for num in nums:
prefix_sum.append(prefix_sum[-1] + num)return merge_sort(0, len(prefix_sum) - 1)
# 示例运行
nums = [-2, 5, -1]
lower = -2
upper = 2
print(countRangeSum(nums, lower, upper)) # 输出：3
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。