(数据量大时通过map维护元素的信息来降低枚举复杂度AtCoder - abc233_d 与AtCoder - abc166_e

简介: (数据量大时通过map维护元素的信息来降低枚举复杂度AtCoder - abc233_d 与AtCoder - abc166_e

E - This Message Will Self-Destruct in 5s (atcoder.jp)


D - Count Interval (atcoder.jp)


求数组中符合某种性质的情况个数,情况包含数组里的两个元素。


这类题的特征是性质可以变换成只包含一个元素的形式


且看上去非常贴合朴素枚举的特征,但数据范围不允许朴素枚举(2e5往上)


f[i] + f[j] == j - i可以换成f[i] + i == j - f[j],可以用map来维护任意一边,然后枚举另外一边


卡壳原因是没总结过这种map维护信息的优化,踩陷阱了


看完题解重做后又卡壳


// 卡壳:混淆了m[i-f[i]]和m.count(i-f[i]),前者返回映射值,如果不存在映射就使其映射值变为默认的0并返回,后者如果存在以i-f[i]为键值的映射则返回1,不存在则返回0(还以为是记数函数),


目录
相关文章
|
6月前
|
存储 容器
List,linkeedlist集合介绍,特点,二者区别,增长因子,去重复
List,linkeedlist集合介绍,特点,二者区别,增长因子,去重复
|
6天前
【每日一题Day215】LC1090受标签影响的最大值 | 贪心+排序+哈希表
【每日一题Day215】LC1090受标签影响的最大值 | 贪心+排序+哈希表
21 0
|
6月前
|
容器
List特点和遍历方式及增长因子论证和去重原理和LinkedList特点
List特点和遍历方式及增长因子论证和去重原理和LinkedList特点
28 0
|
6月前
toArray指定的容量和效率关系
toArray指定的容量和效率关系
35 0
|
9月前
数组双重去重的方式六set去重
数组双重去重的方式六set去重
30 0
|
人工智能 测试技术
cf1653c通过操作让数组序列呈现某种规律 C. Differential Sorting
cf1653c通过操作让数组序列呈现某种规律 C. Differential Sorting
51 0
【每日一题Day101】LC1664生成平衡数组的方案数 | 预处理+枚举
给你一个整数数组 nums 。你需要选择 恰好 一个下标(下标从 0 开始)并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。
58 0
|
vr&ar 网络架构 ice
【每日一题Day46】LC1774最接近目标价格的甜点成本 | 回溯 哈希表
当curCost已经不可能再对最终结果有影响时,即curCost>target 并且res更加接近target(剪枝1)
63 0
合并k个已排序的链表---困难
合并k个已排序的链表---困难
95 0
|
Windows
【CCCC】L2-005 集合相似度 (25分),维护set数组去重,比较统计
【CCCC】L2-005 集合相似度 (25分),维护set数组去重,比较统计
94 0