作者:念毅掷 | 来源:互联网 | 2022-11-30 10:42
今天我得到了一个给定数组和'target'的任务,它是该列表中2个整数的总和.一段时间后,我出来了草案解决方案,但它似乎没有通过所有的测试.算法似乎在[0]两次考虑整数.
def two_sum(numbers, target)
numbers.combination 2 do |a, b|
if a + b == target
return numbers.index(a), numbers.index(b)
end
end
end
print two_sum([1, 2, 3], 4) # Expected [0, 2] *OK
print two_sum([1234, 5678, 9012], 14690) # Expected [1, 2] *OK
print two_sum([2, 2, 3], 4) # Expected [0, 1]) but I get [0, 0]
我试图首先使用.map而不是.combination(2)方法,但结果完全相同: - /
1> Cary Swovela..:
def two_sum(numbers, target)
[*0..numbers.size-1].combination(2).find { |i,j| numbers[i] + numbers[j] == target }
end
two_sum([1234, 5678, 9012], 14690)
#=> [1, 2]
two_sum([1234, 5678, 9012], 14691)
#=> nil
这是一种更有效的方法,当数组很大时可能会很有用.
require 'set'
def two_sum(arr, target)
if target.even?
half = target/2
first = arr.index(half)
if first
last = arr.rindex(half)
return [first, last] unless last.nil? || first == last
end
end
a1, a2 = arr.uniq.partition { |n| n <= target/2 }
s = a2.to_set
n = a1.find { |n| s.include?(target-n) }
n.nil? ? nil : [arr.index(n), arr.index(target-n)]
end
如果target
是甚至我首先检查它的一半是否至少出现两次arr
.如果是这样,我们就完成了(除了确定并返回相关索引).即使该方法在该步骤之后没有终止,也需要该步骤不会导致在执行下一步骤之前需要提前终止.
如果target
是奇数还是偶数是但它的一半出现小于两倍于arr
我构建包含在唯一值的临时数组arr
,然后分区成两个阵列,a1
包含的值不大于target/2
和a2
,含有大于值target/2
.因此,如果两个数字总和为target
1必须在a1
,而另一个必须在a2
.
为了加快计算我然后转换a2
到一组s
通过,然后循环a1
寻找一个值n
,这样的s
包含target-n
.我们来试试吧.
arr = 100_000.times.map { rand(1_000_000) }
puts "target i1 arr[i1] i2 arr[i2] calc time (secs)"
puts "---------------------------------------------------------"
1000.times do
t = Time.now
target = rand(1_000_000)
i1, i2 = two_sum(arr, target)
print "#{target} -> "
print i1.nil? ? "nil " :
"#{i1} #{arr[i1]} #{i2} #{arr[i2]}"
puts " #{(Time.now-t).round(4)} secs"
end
版画
target i1 arr[i1] i2 arr[i2] calc time (secs)
---------------------------------------------------------
215113 -> 41 90943 11198 124170 0.027
344479 -> 0 78758 63570 265721 0.0237
188352 -> 190 79209 39912 109143 0.0275
457 -> nil 0.0255
923135 -> 78 84600 43928 838535 0.0207
59391 -> 2 5779 5454 53612 0.0289
259142 -> 73 58864 29278 200278 0.0284
364486 -> 8049 182243 89704 182243 0.001
895164 -> 13 205843 7705 689321 0.0228
880575 -> 20 440073 6195 440502 0.021
我们看到它arr
不包含两个总和的数字457
.另外,请注意倒数第三行中的非常短的时间.这是因为target
(364486/2 #=> 182243
)的一半至少出现了两次arr
.