I just started learning Ruby not too long ago and was confused with this two-sum algorithm. Basically, the algorithm will return true if there are any two integers in the array that add up to the sum, and false if not. I am familiar with the bsearch method in Ruby, but can't figure out why there is:

match_idx && match_idx != i

Shouldn't it just be:

match_idx != i

Code in question:

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

Thanks!

CodePudding user response：

For a given value of el, match_idx will equal a non-negative integer (an index of arr) if there is an index el2 of arr such that arr[el] arr[el2] == target, else match_idx will equal nil, so you have to make sure match_id is not nil before checking match_idx != i.

Let's see if we can make the method more efficient, considering that the time complexity of sorting is O(nlog(n)), where n is the size of the array.

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

If n is the size of arr, the time complexity to construct the set (effectively the same as that of constructing an underlying hash) is O(n) and the time complexity of determining if the set contains a given value is only slightly worse than O(n).