Bare Algo
搜索算法...
Ctrl+K
前缀和与差分
处理区间和查询与区间批量更新的高效技巧。
算法题
(8)
303. 区域和检索 - 数组不可变
简单
给定一个整数数组 nums,处理多项查询,其功能是:计算索引 left 和 right (包含 left 和 right)之间的 nums 元素的和。
数组
设计
前缀和
304. 二维区域和检索 - 矩阵不可变
中等
给定一个二维矩阵 matrix,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。
数组
设计
矩阵
前缀和
724. 寻找数组的中心下标
简单
给你一个整数数组 nums ,请计算数组的 中心下标 。数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。
数组
前缀和
560. 和为 K 的子数组
中等
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。
数组
哈希表
前缀和
974. 和可被 K 整除的子数组
中等
给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的(连续、非空)子数组的数目。
数组
哈希表
前缀和
525. 连续数组
中等
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。
数组
哈希表
前缀和
1094. 拼车
中等
车上最初有 capacity 个空座位。车 只能 向一个方向行驶。给定一个行程计划 trips , trip[i] = [numPassengers_i, from_i, to_i] 表示第 i 次旅行有 numPassengers_i 位乘客,接他们和放他们的位置分别是 from_i 和 to_i 。
数组
排序
堆
模拟
前缀和
1109. 航班预订统计
中等
这里有 n 个航班,它们分别从 1 到 n 进行编号。有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [first_i, last_i, seats_i] 意味着在从 first_i 到 last_i 的每个航班上预订了 seats_i 个座位。
数组
前缀和
实际应用
(4)
埋点/监控区间统计
简单
在前端埋点或监控系统中,利用前缀和快速计算任意时间段内的点击量、PV/UV、或错误计数。避免每次查询都重新遍历原始日志数组。
前缀和
数据分析
统计
批量日程更新
中等
在日历、排期表或容量图中,需要对某个时间段内的所有时间点进行批量加减操作(如批量预订会议室)。使用差分数组将 O(N) 的更新操作优化为 O(1)。
差分数组
日历
排期
滚动定位与锚点
中等
处理不定高列表的滚动定位时,维护累积高度数组(prefixSum)。通过二分查找快速找到对应 scrollTop 的元素索引,或计算页面锚点的精确位置。
前缀和
二分
虚拟列表
滚动
热区覆盖与合并
困难
在处理页面热力图、元素覆盖关系或排期冲突检测时,利用扫描线思路(配合差分思想)计算重叠区域的层数或合并连续区间。
扫描线
差分
可视化
碰撞检测