对Codility演示测试感到困惑

Question

我参加了Codility.com demo test。

我的程序在一个单元测试中返回了错误的值：

TEST extreme_large_numbers 测试算术溢出的极大数序列。 TIME 0.056 秒。 RESULT 错误答案 得到2，但它不是平衡点，sum[0..1]=4294967294，sum[3..3]=-2

好的，由于一开始我无法看到代码中的问题，所以我尝试在Visual Studio项目中运行它。然后编译器发现4294967294对于int来说太大了。它需要是uint或long。因此，我将所有内容更改为long，在VS中运行成功。

然而，演示测试不允许您更改函数输入/返回类型为long。

• 2,147,483,647（最大的带符号32位整数）
• 4,294,967,294（Codility.com单元测试给出的数字）

请问有人能解释一下，如果一个int[]中的数据值为4294967294，这个程序怎么可能正常工作？

- JohnB

Answer 1

你只需要考虑到较大的范围来计算结果，最终结果不会超出范围。但是看起来你的解决方案效率不太高，可以在这个问题上实现线性运行时间。

编辑：你可以查看修订历史记录以获取运行速度快且得分100的代码。;-)

- Lucero

---

1. 我同意我的解决方案不是最有效的，但我不是一个出色的程序员，而且只花了30分钟！
2. 我认为你没有回答我的问题；如果我没有足够大的数据类型来存储“4294967294”，我该如何比较值？

- JohnB

1. 我只是指出来而已...
2. 你不需要，那些实际上是负值，但大数值的总和超过了“int”范围。

- Lucero

我明白了... 2147483647 * 2 = 4294967294 他们故意让 int 数据类型溢出了 :( - JohnB

当然是的 - 这就是 Codility 任务的伟大之处：大多数任务非常简单，但需要考虑微妙的问题。 - Lucero

好的！我重新编辑了一下，这样大家就可以查看修改历史以获取剧透信息……;-) - Lucero

Answer 2

这是一个运行速度快且得分100的@Lurcero代码的Swift 2.2版本：

public func solution(inout A : [Int]) -> Int {

let n = A.count

if n == 0 { return -1 }

if n == 1 { return 0 }

var right : Int64 = A.reduce(0, combine: +)

var left : Int64 = 0

for i in 0..<n {

    right -= A[i]

    if left == right {
        return i
    }
    left += A[i]
}

return -1
}

- Bobj-C