Ruby Arrays-есть ли элементы, где сумма элементов слева равна сумме элементов справа?

Question

Ruby Arrays-есть ли элементы, где сумма элементов слева равна сумме элементов справа?

Учитывая массив Ruby, мне нужно найти, существует ли элемент, в котором сумма элементов слева от элемента равна сумме элементов справа от него.

Пример

[1,2,3,3]

Элемент равен 3, потому что сумма элементов слева от 3 [1,2] равна сумме элементов справа от 3.

Я не знаю, как решить эту проблему, но я попробую.

def left_equal_right(array)

  array.any? do |x|

    index = array.index(x)

    array[0..index-1].inject(:+) == array[index+1..-1].inject(:+)

  end

end



array.any?([1,2,3,3])

=> returns true, but I'm not sure this method works for larger arrays.

476 4

arrays ruby

4 ответов:

Comments

Ничего не найдено.

Cary Swoveland · Accepted Answer · 2014-11-13 20:35:12

Это похоже на решение @Max, хотя я могу завершить поиск раньше, когда все элементы в массиве неотрицательны. Это потому, что разница между правой суммой и левой суммой будет монотонно уменьшаться по мере прохождения через массив.
Мой ответ предполагает, что должен быть по крайней мере один элемент на каждой стороне, но он, конечно, может быть изменен, чтобы разрешить ноль элементов на одной стороне.
Код
def balance(arr)
  return nil if arr.size < 3
  all_non_neg = (arr.min >= 0)
  enum = arr.to_enum
  last = enum.next
  diff = arr.reduce(:+)-last
  (1..arr.size-2).each do |i|
    val = enum.next
    diff += -last - val
    return i if diff.zero?
    return -i if all_non_neg && diff < 0
    last = val
  end
  nil
end
Здесь, когда поиск завершается рано, я возвращаю отрицательный индекс, где это происходит. Это только для иллюстрации; nil было бы более уместно.

Примеры
balance [1,1,1,1,1]                 #=> 2
balance [-1,-1,-1]                  #=> 1
balance [3,4,-6,7,5,-6,4,3,5,2]     #=> 4
balance [3,4,-6,7,5,-6,4,3,5,2,4,7] #=> nil
balance [3,7,2,28,6,5,8,7]          #=> 1
balance [3,7,2,28,6,5,8,7]          #=> -4
Как указано, в последнем примере поиск был завершен по индексу 4.

Max · Accepted Answer · 2014-11-12 02:07:45

Это должно быть быстрее всего, так как он не суммирует весь массив каждую итерацию:
def left_equal_right ary
  left = 0
  right = ary.reduce(:+)

  ary.each do |x|
    right -= x
    return true if left == right
    left += x
  end

  false
end
На моей виртуальной машине это проверяет массив из 10 миллионов элементов за 2 секунды.

tlehman · Accepted Answer · 2014-11-11 20:59:49

Работает для массивов длиной 10 000 (всего несколько секунд)

Тайм-аут для массивов длиной 100 000
left_equal_right (1..100_000).to_a
# =Execution timed out.
Однако, если вы измените свой код следующим образом:
def left_equal_right(array)
  array.any? do |x|
    index = array.index(x)

    left_sum = 0
    right_sum = 0
    left_index = 0
    right_index = 0
    while left_index < index
      left_sum += array[left_index]
      left_index += 1
    end

    while right_index < array.count
      right_sum += array[right_index]
      right_index += 1
    end
    return left_sum == right_sum
  end
end
Тогда вы можете обрабатывать гораздо большие массивы, я пробовал до 10 миллионов:
left_equal_right (1..10_000_000).to_a
# ==> false

Mark Reed · Accepted Answer · 2014-11-11 23:36:10

Попробуйте это-лучший способ получить индексы:
array.each_index.any? do |i|
  array[0..i-1].inject(:+) == array[i+1..-1].inject(:+)
end
Это все еще делает много ненужно повторяющейся работы, но он получает работу и избегает проблемы, которую ваше решение вводит с помощью Array#index.