树状数组-327. 区间和的个数
2022/7/5 23:20:36
本文主要是介绍树状数组-327. 区间和的个数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
问题描述
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中,值位于范围 [lower, upper] (包含 lower 和 upper)之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中,位置从 i 到 j 的元素之和,包含 i 和 j (i ≤ j)。
示例 1:
输入:nums = [-2,5,-1], lower = -2, upper = 2
输出:3
解释:存在三个区间:[0,0]、[2,2] 和 [0,2] ,对应的区间和分别是:-2 、-1 、2 。
示例 2:
输入:nums = [0], lower = 0, upper = 0
输出:1
提示:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
-105 <= lower <= upper <= 105
题目数据保证答案是一个 32 位 的整数
问题求解
(j, i]: presum[i] - presum[j]
对于presum[i],求解满足: lower <= presum[i] - presum[j] <= upper and j < i的j的个数
等价于 presum[i] - uppper <= presum[j] <= presum[i] - lower and j < i的j的个数
因此可以使用排序离散化,计频数组求和的方式来解决。
需要主要的有两点:1)离散化的时候需要将所有涉及的数字进行离散化;2)树状数组的更新要在求解后。
from sortedcontainers import SortedSet class Solution: def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int: n = len(nums) presum = [0] * n presum[0] = nums[0] for i in range(1, n): presum[i] = presum[i - 1] + nums[i] # (j, i]: presum[i] - presum[j] # 对于presum[i],求解满足: lower <= presum[i] - presum[j] <= upper and j < i的j的个数 # 等价于 presum[i] - uppper <= presum[j] <= presum[i] - lower and j < i的j的个数 # 离散化 sort = SortedSet() for num in presum: sort.add(num) sort.add(num - lower) sort.add(num - upper) record = {} rank = 1 for num in sort: record[num] = rank rank += 1 bit = [0] * (len(record) + 1) def update(idx, delta): while idx < len(bit): bit[idx] += delta idx += (idx & -idx) def query(idx): res = 0 while idx: res += bit[idx] idx -= (idx & -idx) return res res = 0 for i in range(n): if lower <= presum[i] <= upper: res += 1 # 由于j < i,因此要讲update放在后面,不然就将本轮的数加入了j的计算当中 r, l = record[presum[i] - lower], record[presum[i] - upper] res += query(r) - query(l - 1) update(record[presum[i]], 1) return res
这篇关于树状数组-327. 区间和的个数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署