如何針對ruby中的Two_sum代碼優化解決方案

Question

我對以下問題的解決方案感到驚訝。

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/後提交的紅寶石解決方案。

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 

我的提交失敗，消息：超出時間限制。任何人都可以指出錯誤並幫助我優化代碼？

Answer 1

我已經修改 如果（hash.find {|鍵，VAL |鍵==值}）行 到 如果（hash.key（價值）？） 來查找哈希中是否存在特定的密鑰，並解決了這個問題。

Answer 2

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]] 

Answer 3

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 

具有當發現匹配並且所以希望不會超時停止執行的優點。 :)

Answer 4

代碼

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]