不久前我剛剛開始學習 Ruby，并且對這種二和演算法感到困惑。基本上，如果陣列中有任何兩個整數相加等于和，則演算法將回傳 true，否則回傳 false。我熟悉 Ruby 中的 bsearch 方法，但無法弄清楚為什么會出現：
match_idx && match_idx != i
不應該只是：
match_idx != i
有問題的代碼：
def okay_two_sum_b(arr, target)
arr = arr.sort
arr.each_with_index do |el, i|
match_idx = arr.bsearch_index { |el2| (target - el) <=> el2 }
return true if match_idx && match_idx != i
end
false
end
arr = [0, 1, 5, 7]
p bad_sum(arr, 6) # => should be true
p bad_sum(arr, 10) # => should be false
謝謝！
uj5u.com熱心網友回復：
對于給定的值el，match_idx將等于一個非負整數（的指標arr），如果有一個索引el2的arr，這樣arr[el] arr[el2] == target，否則match_idx將等于nil，所以你必須確保match_id不nil檢查前match_idx != i。
考慮到排序的時間復雜度為 O(nlog(n))，其中 n 是陣列的大小，讓我們看看是否可以使該方法更高效。
require 'set'
def two_sum?(arr, target)
return true if target.even? && (arr.count(target/2) > 1)
st = arr.to_set
st.each do |e|
f = target-e
return true if e != f && st.include?(f)
end
false
end
two_sum?([0, 1, 5, 7], 6) #=> true
two_sum?([0, 1, 5, 7], 10) #=> false
如果 n 是 的大小arr，則構造集合的時間復雜度（實際上與構造底層散列的時間復雜度相同）為 O(n) 并且確定集合是否包含給定值的時間復雜度僅比 O 稍差(n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/370149.html
標籤：红宝石