Ruby数组 - 是否存在任何元素，其左侧元素的和等于右侧元素的和？

Question

给定一个 Ruby 数组，我需要找到是否存在一个元素，使得该元素左侧的元素之和等于右侧的元素之和。

例子：

[1,2,3,3]

这个元素是3，因为左侧元素[1,2]的总和等于右侧元素的总和。

我不确定怎么解决，但我会尝试一下。

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.

- Darkmouse

---

如果您不确定它是否适用于更大的数组，那么...请尝试使用更大的数组？我对您为什么要问一个工作解决方案的问题感到困惑。此外，这是一个打字错误吗？array.any?([1,2,2,3])，因为您实际上没有调用您的例程。 - Brennan

当可能存在重复元素时，请勿使用array.index。它只会找到第一个。 - Mark Reed

是的，那是一个错误。我想说的是[1,2,3,3]。感谢指出。 - Darkmouse

@Mark Reed，非常好的建议。索引无法处理重复值。感谢您指出这一点。 - Darkmouse

Answer 1

这应该是最快的，因为它不会在每次迭代时对整个数组进行求和：

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

在我的虚拟机上，这个程序在 2 秒内检查了一个包含 1000 万元素的数组。

- Max

---

这看起来像是一个O(n)的解决方案，很不错。我想我的只有O(n^2)。干得好。 - Darkmouse

有人可能认为，如果还想知道发生平衡的索引位置，那么 return true if left == right 可以简单地改为 return i if left == right，但这是行不通的，因为这会产生：left_equal_right [0,1,-1] #=> 0。 - Cary Swoveland

@Ajedi32，说得好。我想这取决于OP所说的“左侧元素之和等于右侧元素之和”的含义。在我的答案中，我假设每一侧都必须至少有一个元素，但是，根据应用程序的不同，任何一种解释都可能是合适的。 - Cary Swoveland

我选择这个问题的解释只是因为它的代码短而且可爱。 :P - Max

Answer 2

处理长度为10000的数组时速度较快（仅需几秒钟）

处理长度为100000的数组时会超时

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

那么您就可以处理更大的数组，我试过最多达到1000万：

left_equal_right (1..10_000_000).to_a
# ==> false

- tlehman

Answer 3

试试这个 - 更好的获取索引的方法：

array.each_index.any? do |i|
  array[0..i-1].inject(:+) == array[i+1..-1].inject(:+)
end

这个方法仍然做了很多不必要的重复工作，但它完成了工作并避免了你的解决方案所引入的问题，它使用了Array#index。

- Mark Reed

---

这解决了初始解只找到第一个元素索引的问题，当存在重复元素时。 - Brennan

在这里使用each_index会稍微更清晰一些。@DarkMouse - _表示这个变量不会被使用 - 一些集成开发环境会抱怨局部变量未被使用。 - BroiSatse

@DarkMouse - 不完全准确。块的行为更像是proc而不是lambda，如果它接收到与预期不同数量的参数，它永远不会引发错误。 - BroiSatse

@MarkReed - 另外array[0..i-1]可以写成array.first(i)，而array[i+1..-1]可以写成array.last(array.size - i - 1) - 有些人可能会觉得这样更能描述清楚。 - BroiSatse

@BroiSatse 谢谢，但我只是从 OP 的代码中复制并粘贴，只更改了必须更正问题的部分，而不是追求最大程度的 Ruby 语言习惯。无论如何，我会使用 array.drop(i+1)。 - Mark Reed

Answer 4

这与@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处终止。

- Cary Swoveland