如何在 Lua 中以最小的时间复杂度检查表中是否存在相似元素

哈希表是一个好方法（即普通的Lua表）。只需循环每个整数并将其作为键放入表中，但首先检查键是否已经存在。如果存在，则有重复值。就像这样：

values = { 1, 2, 3, 4, 5, 1 } -- 输入值

local htab = {}
for _, v in ipairs(values) do
  if htab[v] then print('duplicate value: ' .. v)
  else htab[v] = true end
end

对于小的整数值，表会使用数组，因此访问会是O(1)。对于更大且因此更稀疏的值，值将在表的哈希表部分中，这也可以假定为O(1)。由于您需要插入N个值，因此这是O(N)。

在O(N)之上变得更快似乎不可能，因为您必须至少访问列表中的每个值一次。