如何提高嵌套循环的算法效率

Question

给定一个整数列表和一个和值,返回前两个值(从左边)加起来形成总和.

例如,给定:

sum_pairs([10, 5, 2, 3, 7, 5], 10)

[5, 5](在索引[1, 5]处[10, 5, 2, 3, 7, 5])加起来10,和[3, 7](在索引处[3, 4])加起来10.其中,整个对[3, 7]更早,因此是正确的答案.

这是我的代码:

def sum_pairs(ints, s)
  result = []
  i = 0
  while i < ints.length - 1
    j = i+1
    while j < ints.length
      result << [ints[i],ints[j]] if ints[i] + ints[j] == s
      j += 1
    end
    i += 1
  end
  puts result.to_s
  result.min
end

它工作正常,但效率太低,需要12000毫秒才能运行.嵌套循环是效率低下的问题.我怎么能改进算法？

Answer 1

• 有Set你看过的数字,从空开始
• 查看输入列表中的每个数字
• 计算您需要添加到哪个数字以构成总和
• 查看该号码是否在集合中
• 如果是,则返回它和当前元素
• 如果没有,请将当前元素添加到集合中,然后继续循环
• 当循环结束时,你确定没有这样的一对; 任务没有指定,但返回nil可能是最佳选择

应该超高速,因为只有一个循环.一旦找到第一个匹配对,它也会终止,所以通常在得到答案之前你甚至都不会查看每个元素.

作为一种风格的东西,while以这种方式使用是非常unububish.在实施上述内容时,我建议你使用ints.each do |int| ... end而不是while.

编辑:正如Cary Swoveland评论的那样,出于一个奇怪的原因,我认为你需要的是指数,而不是价值观.