如何在ruby中优化Two_sum代码的解决方案
我正在解决以下问题的解决方案。
Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. 这是在引用C ++代码http://leetcodeunlock.com/2016/05/20/leetcode-1-two-sum-easy/之后在ruby中提交的解决方案。
def two_sum(nums, target) hash = {} arr = [] nums.each_with_index do |value,index| y = target - value if(hash.find{|key,val| key == value}) arr << hash[value] arr << index return arr else hash[y] = index end end end
我的提交失败，显示消息：超出时间限制。 任何人都可以指出错误并帮助我优化代码吗？
nums = [2, 7, 11, 15] target = 9 # this will find all combinations of 2 elements that add up to 9 results = (0...nums.size).to_a.combination(2).select { |first, last| nums[first] + nums[last] == target } results.first #=> [0, 1]
代码的某些部分的说明：
# Get indexes of all elements of nums array (0...nums.size).to_a #=> [0, 1, 2, 3] # Generate all combinations of indexes of each 2 elements (0...nums.size).to_a.combination(2).to_a #=> [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
我已经修改了行if（hash.find {| key，val | key == value}）到if（hash.key？（value））以查找散列中是否存在特定键，这解决了问题。
码
def sum_to_num(arr, num) return [num/2, num/2] if num.even? && arr.count(num/2) > 1 a = arr.uniq. group_by { |n| (2*n-num).abs }. find { |_,a| a.size > 1 } a.nil? ? nil : a.last end
这个方法需要三次或四次通过数组，如果num是偶数，一个用于计数num/2的实例，一个用于删除重复值，一个用于group_by ，一个用于find总和为所需总数的数字对。 因此，它应该比评估每对数组元素的方法快得多，特别是当数组的大小增加时。
例子
sum_to_num [2, 11, 7, 15], 9 #=> [2, 7] sum_to_num [2, 5, 2, 6, 1, -5, 4], 10 #=> [6, 4] sum_to_num [2, 7, 11, -7, 15], 0 #=> [7, -7] sum_to_num [2, 7, 11, 7, 15], 14 #??? sum_to_num [2, -7, 11, -7, 15], -14 #??? sum_to_num [2, 7, 11, 15], 17 #=> [2, 15] sum_to_num [2, -11, 8, 15], 4 #=> [-11, 15] sum_to_num [2, -11, 8, 15], -3 #=> [-11, 8] sum_to_num [2, -11, 8, 15], 100 #=> nil
说明
假设x和y总和为num 。 然后
2*x-num + 2*y-num = 2*(x+y) - 2*num = 2*num - 2*num = 0
意味着2*x-num和2*y-num要么都是零，要么它们具有相反的符号和相同的绝对值。 同样，如果2*x-num和2*y-num总和为零，那么
2*x-num + 2*y-num = 0 2*(x+y) - 2*num = 0
意味着n+m = num （考虑到2*x+num是线性变换，这并不奇怪。
假设
arr = [2, 5, 2, 6, 1, -5, 4] num = 10
然后
if num.even? && arr.count(num/2) > 1 #=> if 10.even? && arr.count(5) > 1 #=> if true && false #=> false
因此，不要返回[5,5] 。
b = arr.uniq #=> [2, 5, 6, 1, -5, 4] c = b.group_by { |n| (2*n-num).abs } #=> {6=>[2], 0=>[5], 2=>[6, 4], 8=>[1], 20=>[-5]} a = c.find { |_,a| a.size > 1 } #=> [2, [6, 4]] return nil if a.nil? # do not return a.last #=> [6, 4]
def two_sum(nums, target) nums.each_with_index do |value, index| match_index = nums.find_index(target - value) return [index, match_index] if match_index end nil end
上面的优点是，当找到匹配时它会停止执行，因此希望不会超时。 🙂
我为了好玩而做了这个挑战，写了一个清理过的ruby解决方案。
def two_sum(nums, target) hash = {} nums.each_with_index { |number, index| hash[number] = index } nums.each_with_index do |number, index| difference = target - number if hash[difference] && hash[difference] != index return [index, hash[difference]] end end end