Lua实现Two Sum问题遇table.find调用nil值报错求助

先解决你的报错问题 #

你遇到的attempt to call a nil value (field 'find')错误，是因为Lua标准库的table模块根本没有table.find这个函数。要找数组中元素的索引，得自己实现查找逻辑，或者用循环遍历查找。

给你修改后的可运行代码：

num = {2,7,11,15}
target = 9
current = 0 

-- 自定义查找元素索引的函数
local function get_index(arr, val)
    for i, v in ipairs(arr) do
        if v == val then
            return i
        end
    end
    return nil
end

repeat
  createNum1 = num[math.random(1,#num)]
  createNum2 = num[math.random(1,#num)]
  current = createNum1 + createNum2
until current == target

print(get_index(num, createNum1), get_index(num, createNum2))

另外，原代码里tonumber(num[...])是多余的——数组里的元素本身就是数字类型，不需要再转换。

聊聊Two Sum的正确算法思路 #

你现在用的随机数凑数方法完全是碰运气，数组越大，凑到正确结果的概率越低，实际开发中根本不会这么用。下面是两种正经的实现思路：

1. 暴力枚举法 #

最直接的思路：双重循环遍历数组，检查每一对元素的和是否等于target，找到就返回它们的索引。

Lua实现代码：

local function two_sum_bruteforce(arr, target)
    for i = 1, #arr do
        for j = i + 1, #arr do
            if arr[i] + arr[j] == target then
                return i, j
            end
        end
    end
    return nil, nil
end

num = {2,7,11,15}
target = 9
local idx1, idx2 = two_sum_bruteforce(num, target)
print(idx1, idx2) -- 输出 1 2

优点：逻辑简单，不用额外空间；缺点：时间复杂度为O(n²)，数组元素多的时候速度很慢。

2. 哈希表优化法 #

用空间换时间：遍历数组时，用一个Lua表（相当于哈希表）存储已经遍历过的元素及其索引。对每个当前元素，计算需要的补数（target - 当前元素），如果补数已经在哈希表里，说明之前遍历过这个补数，直接返回两个索引即可。

Lua实现代码：

local function two_sum_hash(arr, target)
    local num_map = {}
    for i, v in ipairs(arr) do
        local complement = target - v
        if num_map[complement] then
            return num_map[complement], i
        end
        num_map[v] = i
    end
    return nil, nil
end

num = {2,7,11,15}
target = 9
local idx1, idx2 = two_sum_hash(num, target)
print(idx1, idx2) -- 输出 1 2

优点：时间复杂度O(n)，只需要遍历一次数组；缺点：需要额外的表存储元素，空间复杂度O(n)。

内容的提问来源于stack exchange，提问作者TDumitru