如何提高嵌套循环的算法效率
给定一个整数列表和一个和值，返回前两个值(从左边)，这些值加在一起形成和。
例如，考虑到：
sum_pairs([10, 5, 2, 3, 7, 5], 10)[5, 5] (at indices [1, 5] of [10, 5, 2, 3, 7, 5])加起来是10，[3, 7] (at indices [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毫秒才能运行。嵌套循环是效率低下的问题。如何改进算法？
回答 4
Stack Overflow用户
发布于 2018-10-25 05:09:34
- 有一个你见过的数字的
Set，开始为空 - 查看输入列表中的每个数字
- 计算您需要添加到其中的数字，以构成该总和。
- 看看这个数字是否在集合中
- 如果是，则返回它和当前元素
- 如果没有，则将当前元素添加到集合中，并继续循环。
- 当循环结束时，您可以确定没有这样的对；任务没有指定，但是返回
nil可能是最好的选择。
应该是超快的，因为只有一个循环。它也会在找到第一个匹配对时终止，所以通常在得到答案之前，您甚至不会遍历每个元素。
作为一种样式，以这种方式使用while是非常unRubyish的。在实现上面的内容时，我建议您使用ints.each do |int| ... end而不是while。
编辑:正如凯里·斯沃夫兰( Cary Swoveland )评论的那样，出于一个奇怪的原因，我认为你需要索引，而不是值。
Stack Overflow用户
发布于 2018-10-25 06:25:21
require 'set'
def sum_pairs(arr, target)
s = Set.new
arr.each do |v|
return [target-v, v] if s.include?(target-v)
s << v
end
nil
end
sum_pairs [10, 5, 2, 3, 7, 5], 10
#=> [3, 7]
sum_pairs [10, 5, 2, 3, 7, 5], 99
#=> nil我使用设置方法来加速include?查找(更重要的是，只保存唯一值)。
Stack Overflow用户
发布于 2018-10-25 06:51:35
尝试下面，因为它是更易读的。
def sum_pairs(ints, s)
ints.each_with_index.map do |ele, i|
if ele < s
rem_arr = ints.from(i + 1)
rem = s - ele
[ele, rem] if rem_arr.include?(rem)
end
end.compact.last
endhttps://stackoverflow.com/questions/52981674
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号