Leetcode 327. 区间和的个数

1.题目基本信息

1.1.题目描述

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

1.2.题目地址

https://leetcode.cn/problems/count-of-range-sum/description/

2.解题方法

2.1.解题思路

归并排序。求nums的前缀和数组，并对前缀和数组使用归并排序算法进行排序，在排序过程的归并之前，使用双指针算出rarr[j]-larr[i]在[lower,upper]区间的(i,j)的组合对数，并使用全局变量进行统计总对数，即为题解

3.解题代码

python代码

class Solution: def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int: # 思路1：归并排序。求nums的前缀和数组，并对前缀和数组使用归并排序算法进行排序，在排序过程的归并之前，使用双指针算出rarr[j]-larr[i]在[lower,upper]区间的(i,j)的组合对数，并使用全局变量进行统计总对数，即为题解 n = len(nums) preSums = [0] * (n + 1) for i in range(n): preSums[i + 1] = preSums[i] + nums[i] self.lower = lower self.upper = upper self.result = 0 self.mergeSort(preSums, 0, n) # print(preSums) # print(self.result) return self.result def mergeSort(self, nums:list[int], left:int, right:int): # 第一步，递归将左右两侧进行排序 if left >= right: return mid = (right - left) // 2 + left self.mergeSort(nums, left, mid) self.mergeSort(nums, mid + 1, right) larr = nums[left:mid + 1] rarr = nums[mid + 1:right + 1] # 第二步，找到larr和rarr能够构成的合法情况的对数 i, j1, j2 = 0, 0, 0 while i < mid + 1 - left: while j1 < right - mid and rarr[j1] < larr[i] + self.lower: j1 += 1 while j2 < right - mid and rarr[j2] <= larr[i] + self.upper: j2 += 1 self.result += j2 - j1 i += 1 # 第三步，merge已经排序的部分 i, j, k = 0, 0, left while i < mid + 1 - left and j < right - mid: if larr[i] < rarr[j]: nums[k] = larr[i] i += 1 k += 1 else: nums[k] = rarr[j] j += 1 k += 1 while i < mid + 1 - left: nums[k] = larr[i] i += 1 k += 1 while j < right - mid: nums[k] = rarr[j] j += 1 k += 1

4.执行结果