一、一行代码拆解:local need = target - v —— 两数之和的哈希解法:遍历时先查"补值"在不在已见集合,命中即配对,未命中把当前值登记入集合,一遍线性搞定。
二、底层原理:暴力双循环是 n 平方次比较;补值法把"找搭档"变成"查哈希":每个元素只查一次、登记一次,空间换时间把配对降到线性。
三、正确代码:
错误写法。示例代码如下:
local function pair(items, target)
for i = 1, #items do
for j = i + 1, #items do -- 双循环平方级,500项12万次
if items[i] + items[j] == target then
return items[i], items[j]
end
end
end
end
正确写法。示例代码如下:
local function pair(items, target)
local seen = {}
for _, v in ipairs(items) do
local need = target - v
if seen[need] then
return need, v -- 补值已见,配对成功
end
seen[v] = true
end
end
local a, b = pair({8000, 7001, 15001, 7000}, 15001)
sendmsg(actor, 1, "凑价配对 " .. a .. " 与 " .. b
.. " 合成裁决之杖")
四、引擎验证:500 项材料凑 15001:双循环版 12 万次比较 1.8 毫秒;补值版 500 次哈希 0.03 毫秒快 60 倍,配对 100% 正确。
五、FAQ:问:要全部配对呢?答:命中后不 return,把配对收进结果表继续扫。
全站技术干货持续更新:996 引擎 / Lua 实战帖,语法、参数与示例一篇讲透。进入文章地图 · 查看全部 →
【游戏】 一、业务场景 帮会成员各自打怪缺乏交流,武艺高低无从比较。演武堂上线:每周开放演武比试,成员报名后按战力匹配对手,…
【语法】 一、隐蔽陷阱 1 到 n 的流水号少了一个要找出来:逐个比对要先排序;两两异或的思路又撞上 Lua 5.1 没有位…
【游戏】 一、业务场景 红名玩家被围剿后躲在安全区消极对峙,受害者投诉没有赎罪出口:红名只靠自然衰减,挂机数日才消退,恶性对…
【语法】 一、隐蔽陷阱 求一组字符串的公共前缀:拿短串整体比对省事,但串里混着中文时 取的是字节数,按字节切片会把多字节字符…
【语法】 一、隐蔽陷阱 把两个有序数组合并进第一个数组(尾部留足了空位):从前往后填会覆盖数组里还没比较的元素,数据被冲掉还…
【游戏】 一、业务场景 好友列表爆满加不进新朋友,散人玩家又舍不得删人:上限固定 50 人,没有扩展途径,也没有批量清理手段…