數組中的對象的紅寶石數量等於零

編寫一個方法，用於查找數組數組是否有一個總和爲零的對。小心零的情況;在數組中需要有兩個零來構成一個總和爲零的對。數組中的對象的紅寶石數量等於零

下面是我寫的代碼，但我知道它是錯誤的。我知道在某些時候它會自己添加，所以如果我的數組中只有一個0，那麼它仍然會返回true。我是編程和Ruby的新手，所以任何建議都會非常感激。

謝謝！

def has_zero?(array) 
     left, right = [-1,1] 
     lefter=[] 
     righter=[] 
     righter=array.each {|x| x+= array[right]} 
     lefter=array.each {|x| x+= array[left]} 
     if lefter.include?(0) || righter.include?(0) 
      return true 
     else return false 
     end 
     left,right = [left-1,right+1] 
    end

來源

2013-05-19 JaTo

您的示例輸入數據丟失。證明這一點，以及你的意思是「有一對」。任何兩個數字或兩個連續的數字？ –

任何兩個數字 – JaTo

不知道爲什麼這個問題被關閉爲「太本地化」。這是2-sum問題，這是一個變種：http://en.wikipedia.org/wiki/Subset_sum_problem。 – FMc

Ruby有一些內置的方法，使這很容易：

def has_zero_sum_pair?(a) 
    a.permutation(2).any?{|pair| pair.inject(:+) == 0} 
end

a.permutation(2)爲您提供了a每對。 any?返回true如果塊返回true。 inject(:+)是一種獲取數組總和的簡單方法。

has_zero_sum_pair?([1, 2, 3]) 
# => false 
has_zero_sum_pair?([1, 2, 3, -2]) 
# => true 
has_zero_sum_pair?([1, 2, 3, 0]) 
# => false 
has_zero_sum_pair?([0, 1, 2, 3, 0]) 
# => true

更新：如果我不知道Array#permutation，並曾在浮現在腦海的第一種方式來做到這一點，或者如果我是擔心的表現，我可能會做這樣的事情：

def has_zero_sum_pair2?(a) 
    (0..a.length-2).each do |i| 
    (i+1..a.length-1).each do |j| 
     return true if a[i] + a[j] == 0 
    end 
    end 
    false 
end

我發現醜陋，更容易出錯，而且寫的時間也更長。但小陣列的速度要快四倍，大陣列的速度要快十倍。在編程中，典型的做法是在大多數情況下使用簡單的方法，但在性能上並不理想。有時，如果選擇更好的算法或數據結構，可以獲得更好的性能，而不會導致成本明確。通常需要權衡。

更新2：如果我真的關心表現，我會使用@ FMc的技術。這是使用更好的數據結構和算法獲得巨大性能的好例子。

來源

2013-05-19 17:45:59

我建議在使用它的同時顯示沒有'inject'的版本，以便讓初學者更清楚它正在做什麼:) – hobbs

作爲警告：當數組變大時，'permutation'會變得非常慢。 –

是不是有一個更「初學者」的方式做到這一點，而不使用「排列」？我剛剛開始學習編程上週，我甚至不知道注入方法。謝謝 – JaTo

這個工作除零。

[1, 2, 3, -2] 
.uniq.group_by(&:abs).any?{|_, tuple| tuple.length == 2} 
# => true

來源

2013-05-19 18:00:33 sawa

此問題需要Hash。

vals = [0, 4, 3, 0, -3, 2, -2, 1, 3, -4, -4] 

# Our hash: 
# groups[X] = Array of vals equal to X 
groups = vals.group_by { |v| v } 

# Just check whether the hash contains a pair 
# of keys X and -X, or whether the original array 
# had more than one zero in it. 
p groups.any? { |k, vs| k == 0 ? vs.size > 1 : groups.has_key?(-k) }

您可以通過稍微改變測試推廣到任何target總和：

k == target/2 ? vs.size > 1 : groups.has_key?(target - k)

來源

2013-05-19 18:47:02 FMc

這很聰明，非常非常快。 –

順便說一句：你的'group_by'尖叫stdlib中的身份函數。我通常在我的工具欄中有一個：'ID = - > x {x}'。然後，你的'group_by'變成'vals.group_by（＆ID）'。如果你習慣於說Haskell，那麼'Prelude'中有一個'id'，這就更加可讀。 –

@JörgWMittag是的，我以爲完全一樣！我確信我忽略了一些東西。找到了這個：http://stackoverflow.com/questions/6308470。 – FMc

array = [1,2,3,-2,0,0] 

array.any?{|a| array.rindex(-a) > array.index(a)}

檢查，看看是否有項目的負面是繼數組中的權利。（rindex找到數組中最後一次出現的索引。）

來源

2013-05-19 18:57:40

數組中的對象的紅寶石數量等於零

回答

相關問題