Skip to content

Latest commit

 

History

History
205 lines (196 loc) · 55.5 KB

prefix-sum.md

File metadata and controls

205 lines (196 loc) · 55.5 KB

前缀和

全部标签

数据结构

数组 矩阵 链表 双向链表 单调栈 队列 单调队列 堆(优先队列) 哈希表 字符串 字符串匹配 二叉树 二叉搜索树 最小生成树 有序集合 拓扑排序 最短路 强连通分量 欧拉回路 双连通分量 并查集 字典树 线段树 树状数组 后缀数组

算法

枚举 递归 分治 回溯 贪心 动态规划 排序 桶排序 计数排序 基数排序 归并排序 快速选择 二分查找 记忆化搜索 深度优先搜索 广度优先搜索 双指针 位运算 前缀和 计数 滑动窗口 状态压缩 哈希函数 滚动哈希 扫描线

其他

数学 数论 几何 博弈 模拟 组合数学 随机化 概率与统计 水塘抽样 拒绝采样 数据库 设计 数据流 脑筋急转弯 交互 迭代器 多线程


题号 标题 题解 标签 难度 力扣
209 长度最小的子数组 [✓] 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
238 除自身以外数组的乘积 [✓] 数组 前缀和 🟠 🀄️ 🔗
253 会议室 II 🔒 贪心 数组 双指针 3+ 🟠 🀄️ 🔗
303 区域和检索 - 数组不可变 [✓] 设计 数组 前缀和 🟢 🀄️ 🔗
304 二维区域和检索 - 矩阵不可变 [✓] 设计 数组 矩阵 1+ 🟠 🀄️ 🔗
325 和等于 k 的最长子数组长度 🔒 数组 哈希表 前缀和 🟠 🀄️ 🔗
363 矩形区域不超过 K 的最大数值和 数组 二分查找 矩阵 2+ 🔴 🀄️ 🔗
370 区间加法 🔒 数组 前缀和 🟠 🀄️ 🔗
410 分割数组的最大值 贪心 数组 二分查找 2+ 🔴 🀄️ 🔗
497 非重叠矩形中的随机点 水塘抽样 数组 数学 4+ 🟠 🀄️ 🔗
523 连续的子数组和 数组 哈希表 数学 1+ 🟠 🀄️ 🔗
525 连续数组 数组 哈希表 前缀和 🟠 🀄️ 🔗
528 按权重随机选择 [✓] 数组 数学 二分查找 2+ 🟠 🀄️ 🔗
548 将数组分割成和相等的子数组 🔒 数组 哈希表 前缀和 🔴 🀄️ 🔗
560 和为 K 的子数组 [✓] 数组 哈希表 前缀和 🟠 🀄️ 🔗
644 子数组最大平均数 II 🔒 数组 二分查找 前缀和 🔴 🀄️ 🔗
713 乘积小于 K 的子数组 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
724 寻找数组的中心下标 [✓] 数组 前缀和 🟢 🀄️ 🔗
731 我的日程安排表 II [✓] 设计 线段树 数组 3+ 🟠 🀄️ 🔗
732 我的日程安排表 III 设计 线段树 二分查找 2+ 🔴 🀄️ 🔗
798 得分最高的最小轮调 数组 前缀和 🔴 🀄️ 🔗
813 最大平均值和的分组 数组 动态规划 前缀和 🟠 🀄️ 🔗
848 字母移位 数组 字符串 前缀和 🟠 🀄️ 🔗
862 和至少为 K 的最短子数组 [✓] 队列 数组 二分查找 4+ 🔴 🀄️ 🔗
903 DI 序列的有效排列 字符串 动态规划 前缀和 🔴 🀄️ 🔗
930 和相同的二元子数组 数组 哈希表 前缀和 1+ 🟠 🀄️ 🔗
974 和可被 K 整除的子数组 数组 哈希表 前缀和 🟠 🀄️ 🔗
995 K 连续位的最小翻转次数 位运算 队列 数组 2+ 🔴 🀄️ 🔗
1000 合并石头的最低成本 数组 动态规划 前缀和 🔴 🀄️ 🔗
1004 最大连续1的个数 III [✓] 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
1074 元素和为目标值的子矩阵数量 数组 哈希表 矩阵 1+ 🔴 🀄️ 🔗
1094 拼车 数组 前缀和 排序 2+ 🟠 🀄️ 🔗
1109 航班预订统计 数组 前缀和 🟠 🀄️ 🔗
1124 表现良好的最长时间段 数组 哈希表 2+ 🟠 🀄️ 🔗
1140 石子游戏 II 数组 数学 动态规划 2+ 🟠 🀄️ 🔗
1177 构建回文串检测 位运算 数组 哈希表 2+ 🟠 🀄️ 🔗
1208 尽可能使字符串相等 字符串 二分查找 前缀和 1+ 🟠 🀄️ 🔗
1248 统计「优美子数组」 数组 哈希表 数学 2+ 🟠 🀄️ 🔗
1292 元素和小于等于阈值的正方形的最大边长 数组 二分查找 矩阵 1+ 🟠 🀄️ 🔗
1310 子数组异或查询 位运算 数组 前缀和 🟠 🀄️ 🔗
1314 矩阵区域和 数组 矩阵 前缀和 🟠 🀄️ 🔗
1371 每个元音包含偶数次的最长子字符串 位运算 哈希表 字符串 1+ 🟠 🀄️ 🔗
1413 逐步求和得到正数的最小值 [✓] 数组 前缀和 🟢 🀄️ 🔗
1420 生成数组 动态规划 前缀和 🔴 🀄️ 🔗
1422 分割字符串的最大得分 [✓] 字符串 前缀和 🟢 🀄️ 🔗
1423 可获得的最大点数 数组 前缀和 滑动窗口 🟠 🀄️ 🔗
1442 形成两个异或相等数组的三元组数目 位运算 数组 哈希表 2+ 🟠 🀄️ 🔗
1480 一维数组的动态和 [✓] 数组 前缀和 🟢 🀄️ 🔗
1524 和为奇数的子数组数目 数组 数学 动态规划 1+ 🟠 🀄️ 🔗
1546 和为目标值且不重叠的非空子数组的最大数目 贪心 数组 哈希表 1+ 🟠 🀄️ 🔗
1588 所有奇数长度子数组的和 [✓] 数组 数学 前缀和 🟢 🀄️ 🔗
1589 所有排列中的最大和 贪心 数组 前缀和 1+ 🟠 🀄️ 🔗
1590 使数组和能被 P 整除 [✓] 数组 哈希表 前缀和 🟠 🀄️ 🔗
1658 将 x 减到 0 的最小操作数 数组 哈希表 二分查找 2+ 🟠 🀄️ 🔗
1664 生成平衡数组的方案数 数组 前缀和 🟠 🀄️ 🔗
1674 使数组互补的最少操作次数 数组 哈希表 前缀和 🟠 🀄️ 🔗
1685 有序数组中差绝对值之和 数组 数学 前缀和 🟠 🀄️ 🔗
1687 从仓库到码头运输箱子 线段树 队列 数组 4+ 🔴 🀄️ 🔗
1703 得到连续 K 个 1 的最少相邻交换次数 贪心 数组 前缀和 1+ 🔴 🀄️ 🔗
1712 将数组分成三个子数组的方案数 数组 双指针 二分查找 1+ 🟠 🀄️ 🔗
1732 找到最高海拔 [✓] 数组 前缀和 🟢 🀄️ 🔗
1737 满足三条件之一需改变的最少字符数 哈希表 字符串 计数 1+ 🟠 🀄️ 🔗
1738 找出第 K 大的异或坐标值 位运算 数组 分治 5+ 🟠 🀄️ 🔗
1744 你能在你最喜欢的那天吃到你最喜欢的糖果吗? 数组 前缀和 🟠 🀄️ 🔗
1769 移动所有球到每个盒子所需的最小操作数 [✓] 数组 字符串 前缀和 🟠 🀄️ 🔗
1788 最大化花园的美观度 🔒 贪心 数组 哈希表 1+ 🔴 🀄️ 🔗
1829 每个查询的最大异或值 [✓] 位运算 数组 前缀和 🟠 🀄️ 🔗
1838 最高频元素的频数 贪心 数组 二分查找 3+ 🟠 🀄️ 🔗
1854 人口最多的年份 [✓] 数组 计数 前缀和 🟢 🀄️ 🔗
1856 子数组最小乘积的最大值 数组 前缀和 1+ 🟠 🀄️ 🔗
1862 向下取整数对和 数组 数学 二分查找 1+ 🔴 🀄️ 🔗
1871 跳跃游戏 VII 字符串 动态规划 前缀和 1+ 🟠 🀄️ 🔗
1872 石子游戏 VIII 数组 数学 动态规划 2+ 🔴 🀄️ 🔗
1878 矩阵中最大的三个菱形和 数组 数学 矩阵 3+ 🟠 🀄️ 🔗
1889 装包裹的最小浪费空间 数组 二分查找 前缀和 1+ 🔴 🀄️ 🔗
1893 检查是否区域内所有整数都被覆盖 [✓] 数组 哈希表 前缀和 🟢 🀄️ 🔗
1894 找到需要补充粉笔的学生编号 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
1895 最大的幻方 数组 矩阵 前缀和 🟠 🀄️ 🔗
1915 最美子字符串的数目 位运算 哈希表 字符串 1+ 🟠 🀄️ 🔗
1930 长度为 3 的不同回文子序列 [✓] 位运算 哈希表 字符串 1+ 🟠 🀄️ 🔗
1943 描述绘画结果 数组 哈希表 前缀和 1+ 🟠 🀄️ 🔗
1983 范围和相等的最宽索引对 🔒 数组 哈希表 前缀和 🟠 🀄️ 🔗
1991 找到数组的中间位置 [✓] 数组 前缀和 🟢 🀄️ 🔗
2017 网格游戏 [✓] 数组 矩阵 前缀和 🟠 🀄️ 🔗
2021 街上最亮的位置 🔒 数组 有序集合 前缀和 🟠 🀄️ 🔗
2024 考试的最大困扰度 字符串 二分查找 前缀和 1+ 🟠 🀄️ 🔗
2025 分割数组的最多方案数 数组 哈希表 计数 2+ 🔴 🀄️ 🔗
2055 蜡烛之间的盘子 数组 字符串 二分查找 1+ 🟠 🀄️ 🔗
2067 等计数子串的数量 🔒 字符串 计数 前缀和 🟠 🀄️ 🔗
2083 求以相同字母开头和结尾的子串总数 🔒 哈希表 数学 字符串 2+ 🟠 🀄️ 🔗
2100 适合野炊的日子 数组 动态规划 前缀和 🟠 🀄️ 🔗
2106 摘水果 数组 二分查找 前缀和 1+ 🔴 🀄️ 🔗
2121 相同元素的间隔之和 数组 哈希表 前缀和 🟠 🀄️ 🔗
2132 用邮票贴满网格图 贪心 数组 矩阵 1+ 🔴 🀄️ 🔗
2145 统计隐藏数组数目 数组 前缀和 🟠 🀄️ 🔗
2171 拿出最少数目的魔法豆 贪心 数组 枚举 2+ 🟠 🀄️ 🔗
2207 字符串中最多数目的子序列 贪心 字符串 前缀和 🟠 🀄️ 🔗
2209 用地毯覆盖后的最少白色砖块 字符串 动态规划 前缀和 🔴 🀄️ 🔗
2218 从栈中取出 K 个硬币的最大面值和 数组 动态规划 前缀和 🔴 🀄️ 🔗
2219 数组的最大总分 🔒 数组 前缀和 🟠 🀄️ 🔗
2222 选择建筑的方案数 字符串 动态规划 前缀和 🟠 🀄️ 🔗
2237 计算街道上满足所需亮度的位置数量 🔒 数组 前缀和 🟠 🀄️ 🔗
2245 转角路径的乘积中最多能有几个尾随零 数组 矩阵 前缀和 🟠 🀄️ 🔗
2251 花期内花的数目 数组 哈希表 二分查找 3+ 🔴 🀄️ 🔗
2256 最小平均差 数组 前缀和 🟠 🀄️ 🔗
2270 分割数组的方案数 [✓] 数组 前缀和 🟠 🀄️ 🔗
2271 毯子覆盖的最多白色砖块数 贪心 数组 二分查找 2+ 🟠 🀄️ 🔗
2281 巫师的总力量和 数组 前缀和 1+ 🔴 🀄️ 🔗
2302 统计得分小于 K 的子数组数目 数组 二分查找 前缀和 1+ 🔴 🀄️ 🔗
2381 字母移位 II [✓] 数组 字符串 前缀和 🟠 🀄️ 🔗
2382 删除操作后的最大子段和 并查集 数组 有序集合 1+ 🔴 🀄️ 🔗
2389 和有限的最长子序列 贪心 数组 二分查找 2+ 🟢 🀄️ 🔗
2391 收集垃圾的最少总时间 数组 字符串 前缀和 🟠 🀄️ 🔗
2398 预算内的最多机器人数目 队列 数组 二分查找 4+ 🔴 🀄️ 🔗
2406 将区间分为最少组数 [✓] 贪心 数组 双指针 3+ 🟠 🀄️ 🔗
2420 找到所有好下标 数组 动态规划 前缀和 🟠 🀄️ 🔗
2428 沙漏的最大总和 数组 矩阵 前缀和 🟠 🀄️ 🔗
2438 二的幂数组中查询范围内的乘积 位运算 数组 前缀和 🟠 🀄️ 🔗
2439 最小化数组中的最大值 贪心 数组 二分查找 2+ 🟠 🀄️ 🔗
2448 使数组相等的最小开销 贪心 数组 二分查找 2+ 🔴 🀄️ 🔗
2483 商店的最少代价 字符串 前缀和 🟠 🀄️ 🔗
2485 找出中枢整数 数学 前缀和 🟢 🀄️ 🔗
2488 统计中位数为 K 的子数组 数组 哈希表 前缀和 🔴 🀄️ 🔗
2489 固定比率的子字符串数 🔒 哈希表 数学 字符串 1+ 🟠 🀄️ 🔗
2528 最大化城市的最小电量 贪心 队列 数组 3+ 🔴 🀄️ 🔗
2536 子矩阵元素加 1 数组 矩阵 前缀和 🟠 🀄️ 🔗
2552 统计上升四元组 树状数组 数组 动态规划 2+ 🔴 🀄️ 🔗
2559 统计范围内的元音字符串数 [✓] 数组 字符串 前缀和 🟠 🀄️ 🔗
2574 左右元素和的差值 数组 前缀和 🟢 🀄️ 🔗
2587 重排数组以得到最大前缀分数 贪心 数组 前缀和 1+ 🟠 🀄️ 🔗
2588 统计美丽子数组数目 位运算 数组 哈希表 1+ 🟠 🀄️ 🔗
2602 使数组元素全部相等的最少操作次数 数组 二分查找 前缀和 1+ 🟠 🀄️ 🔗
2615 等值距离和 数组 哈希表 前缀和 🟠 🀄️ 🔗
2640 一个数组所有前缀的分数 数组 前缀和 🟠 🀄️ 🔗
2680 最大或值 贪心 位运算 数组 1+ 🟠 🀄️ 🔗
2681 英雄的力量 数组 数学 动态规划 2+ 🔴 🀄️ 🔗
2731 移动机器人 脑筋急转弯 数组 前缀和 1+ 🟠 🀄️ 🔗
2772 使数组中的所有元素都等于零 数组 前缀和 🟠 🀄️ 🔗
2819 购买巧克力后的最小相对损失 🔒 数组 二分查找 前缀和 1+ 🔴 🀄️ 🔗
2838 英雄可以获得的最大金币数 🔒 数组 双指针 二分查找 2+ 🟠 🀄️ 🔗
2845 统计趣味子数组的数目 数组 哈希表 前缀和 🟠 🀄️ 🔗
2848 与车相交的点 数组 哈希表 前缀和 🟢 🀄️ 🔗
2875 无限数组的最短子数组 数组 哈希表 前缀和 1+ 🟠 🀄️ 🔗
2906 构造乘积矩阵 数组 矩阵 前缀和 🟠 🀄️ 🔗
2947 统计美丽子字符串 I 哈希表 数学 字符串 3+ 🟠 🀄️ 🔗
2949 统计美丽子字符串 II 哈希表 数学 字符串 2+ 🔴 🀄️ 🔗
2950 可整除子串的数量 🔒 哈希表 字符串 计数 1+ 🟠 🀄️ 🔗
2955 同端子串的数量 🔒 数组 哈希表 字符串 2+ 🟠 🀄️ 🔗
2968 执行操作使频率分数最大 数组 二分查找 前缀和 2+ 🔴 🀄️ 🔗
2971 找到最大周长的多边形 贪心 数组 前缀和 1+ 🟠 🀄️ 🔗
2983 回文串重新排列查询 哈希表 字符串 前缀和 🔴 🀄️ 🔗
3015 按距离统计房屋对数目 I 广度优先搜索 前缀和 🟠 🀄️ 🔗
3017 按距离统计房屋对数目 II 前缀和 🔴 🀄️ 🔗
3026 最大好子数组和 数组 哈希表 前缀和 🟠 🀄️ 🔗
3028 边界上的蚂蚁 数组 前缀和 模拟 🟢 🀄️ 🔗
3070 元素和小于等于 k 的子矩阵的数目 数组 矩阵 前缀和 🟠 🀄️ 🔗
3077 K 个不相交子数组的最大能量值 数组 动态规划 前缀和 🔴 🀄️ 🔗
3086 拾起 K 个 1 需要的最少行动次数 贪心 数组 前缀和 1+ 🔴 🀄️ 🔗
3096 得到更多分数的最少关卡数目 数组 前缀和 🟠 🀄️ 🔗
3104 查找最长的自包含子串 🔒 哈希表 字符串 二分查找 1+ 🔴 🀄️ 🔗
3129 找出所有稳定的二进制数组 I 动态规划 前缀和 🟠 🀄️ 🔗
3130 找出所有稳定的二进制数组 II 动态规划 前缀和 🔴 🀄️ 🔗
3147 从魔法师身上吸取的最大能量 数组 前缀和 🟠 🀄️ 🔗
3152 特殊数组 II [✓] 数组 二分查找 前缀和 🟠 🀄️ 🔗
3179 K 秒后第 N 个元素的值 数组 数学 组合数学 2+ 🟠 🀄️ 🔗
3191 使二进制数组全部等于 1 的最少操作次数 I 位运算 队列 数组 2+ 🟠 🀄️ 🔗
3212 统计 X 和 Y 频数相等的子矩阵数量 数组 矩阵 前缀和 🟠 🀄️ 🔗
3224 使差值相等的最少数组改动次数 数组 哈希表 前缀和 🟠 🀄️ 🔗
3225 网格图操作后的最大分数 数组 动态规划 矩阵 1+ 🔴 🀄️ 🔗
3250 单调数组对的数目 I 数组 数学 动态规划 2+ 🔴 🀄️ 🔗
3251 单调数组对的数目 II 数组 数学 动态规划 2+ 🔴 🀄️ 🔗
3261 统计满足 K 约束的子字符串数量 II 数组 字符串 二分查找 2+ 🔴 🀄️ 🔗
3279 活塞占据的最大总区域 🔒 数组 哈希表 字符串 3+ 🔴 🀄️ 🔗
3312 查询排序后的最大公约数 数组 哈希表 数学 5+ 🔴 🀄️ 🔗
剑指 Offer 66 构建乘积数组 [✓] 数组 前缀和 🟠 🀄️
剑指 Offer II 10 和为 k 的子数组 [✓] 数组 哈希表 前缀和 🟠 🀄️
剑指 Offer II 11 0 和 1 个数相同的子数组 数组 哈希表 前缀和 🟠 🀄️
剑指 Offer II 12 左右两边子数组的和相等 [✓] 数组 前缀和 🟢 🀄️
剑指 Offer II 13 二维子矩阵的和 设计 数组 矩阵 1+ 🟠 🀄️
剑指 Offer II 71 按权重生成随机数 数组 数学 二分查找 2+ 🟠 🀄️
剑指 Offer II 8 和大于等于 target 的最短子数组 [✓] 数组 二分查找 前缀和 1+ 🟠 🀄️
面试题 17.05 字母与数字 数组 哈希表 前缀和 🟠 🀄️
面试题 17.24 最大子矩阵 数组 动态规划 矩阵 1+ 🔴 🀄️