Ruby运行时中的二和算法不会传递给LeetCode

Question

我试图得到一个两和算法来传递LeetCode，但遇到了时间限制，导致它失败。

我不知道如何使我的代码更快地通过。在这个问题中，我得到了一个整数数组（nums）和一个目标值，nums数组中的两个数字必须求和。找到这些数字后，以数组的形式返回它们的索引值。

def two_sum(nums, target)
  numbers_hash = Hash[(0...nums.size).zip(nums)]
  numbers_hash.delete_if do |k, v|
    key_indicies = ((numbers_hash.select { |ki,vi| vi == (target - v) }.keys) - [k])
    key_indicies.empty? ? true : (return [k, key_indicies].flatten)
  end
  return "Couldn't find target value"
end

我可以保留原始的Nums数组，并在一个循环中使用delete_if来修改迭代数组，并在找到正确的目标值时返回。我更喜欢使用散列方法，因为它更具可读性，而且我不认为将数组转换为散列的时间限制太大。

Answer 1

请参阅下面我的解决方案：它的效率更高，比所有Ruby提交的两个总和的25.43%快292毫秒，比所有Ruby提交的100%少使用9.5MB。值得一看。很简单。

def two_sum(nums, target)
    nums.each_with_index do |num,index|
       if nums.include?(target - num)
           return [index,nums.find_index(target - num)] if index != nums.find_index(target - num)
       end
    end         
end

Answer 2

经过一段时间的思考，我意识到我是从错误的方向来处理这个问题的。我应该一个接一个地向哈希表中添加元素，每次在添加新的key:value之前检查解决方案是否存在，而不是从一开始就构建一个潜在的巨大哈希表

def two_sum(nums, target)
  numbers_hash = {}
  nums.each_with_index do |number, index|
    numbers_hash[index] = number
    hash_key = ((numbers_hash.select { |k,v| v == (target - number) }.keys) - [index])
    hash_key.empty? ? false : (return [hash_key, index].flatten)
  end
  return "Couldn't find target value"
end

这比我以前的解决方案运行得快得多。

Answer 3

人们指出ternaries的问题的原因是，它通常表明您正在使一个过程过度复杂化。你在检查它是否为零。但是，在尽量减少行的使用时，会使您自己的代码更难阅读，尽管它在集成到更复杂的代码结构中时可能会“起作用”，但对您自己来说，以后阅读也绝对是一场噩梦。

def two_sum(nums, target)
    search = {}
    nums.each_with_index do |num,i| 
      return [search[target-num], i] unless search[target-num].nil?
      search[num] = i 
    end
end

比这更容易理解，也更容易进行后续审查：

def two_sum(a,g)s={};a.each_with_index{|n,i|s[g-n]==nil ?s[n]=i:(return[s[g-n],i])}end

尽管如此，它们本质上是完全相同的。