一个序列的平衡点是这样的，它的左边的所有的元素的和应该等于右边的所有的元素的和，比如在下面的序列A：
A[0] = -7 A[1] = 1 A[2] = 5A[3] = 2 A[4] = -4 A[5] = 3A[6] = 0
3是一个平衡点因为:
- A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
6也是一个平衡点因为:
- A[0] + A[1] + A[2] + A[3] + A[4] + A[5] = 0
(零个元素的和是零) 索引7不是平衡点，因为它不是序列A的有效索引。
如果你仍然不是很清楚，那么这里给出了明确的定义：0 ≤ k < n 并且 sum[i=0]k-1A[i] = sum[i=k+1]n-1 A[i]。时， 整数k是序列A[0], A[1], ..., A[n−1]$ 的平衡点，这里我们假定零个元素的和为零。
请写一个函数
int equi(int A[], int N);
返回给定序列的平衡点(任意一个)如果没有平衡点则返回−1，假设这个序列可达到非常大。
假定:
- N 是 [0..10,000,000] 内的 整数;
- 数组 A 每个元素是取值范围 [−2,147,483,648..2,147,483,647] 内的 整数 .
复杂度:
- 最坏-情况下，期望的时间复杂度是 O(N);
- 最坏-情况下，期望的空间复杂度是 O(N), 输入存储除外 (不计输入参数所需的存储空间).
输入数组中的元素可以修改
C#给出两个思路一样只是写法有点不同的方法：
方法一：
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 class Solution { 5 public int equi ( int[] A ) { 6 if (A.Length <= 2) 7 return -1; 8 long summary = A.Sum(); 9 long left = 0;10 11 for (int i = 1; i < A.Length; i++)12 {13 left += A[i - 1];14 if (A[i] == left && summary - left - A[i] == A[i])15 return i;16 }17 return -1;18 }19 } 方法二：
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 class Solution { 5 public int equi ( int[] A ) { 6 if (A.Length == 0) 7 return -1; 8 long summary = A.Sum(); 9 10 long sum_left = 0;11 for (int i = 0; i < A.Length; i++)12 {13 long sum_right = summary - sum_left - A[i];14 if (sum_left == sum_right)15 {16 return i;17 }18 sum_left += A[i];19 }20 return -1;21 }22 } 这两种写法优劣请大家一起来评判一下。
========================华丽的分割线==========================
测试网站上给出的评判：
方法一：
Analysis
| test | time | result |
|---|---|---|
| example Test from the task description | 0.080 s. | OK |
| simple | 0.080 s. | OK |
| extreme_large_numbers Sequence with extremly large numbers testing arithmetic overflow. | 0.070 s. | RUNTIME ERROR tested program terminated unexpectedly stdout: Unhandled Exception: System.OverflowException: Number overflow. at System.Linq.Enumerable. |
| overflow_tests | 0.080 s. | RUNTIME ERROR tested program terminated unexpectedly stdout: Unhandled Exception: System.OverflowException: Number overflow. at System.Linq.Enumerable. |
| one_large one large number at the end of the sequence | 0.070 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 0 |
| sum_0 sequence with sum=0 | 0.070 s. | OK |
| single single number | 0.070 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 0 |
| empty Empty array | 0.060 s. | OK |
| combinations_of_two multiple runs, all combinations of {-1,0,1}^2 | 0.080 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 0 |
| combinations_of_three multiple runs, all combinations of {-1,0,1}^3 | 0.080 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 0 |
| small_pyramid | 0.070 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 42 |
| large_long_sequence_of_ones | 0.130 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 50000 |
| large_long_sequence_of_minus_ones | 0.110 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 50002 |
| medium_pyramid | 0.090 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 402 |
| large_pyramid Large performance test, O(n^2) solutions should fail. | 0.160 s. | WRONG ANSWER got -1, but equilibrium point exists, for example on position 898 |
方法二：
Analysis
Detected time complexity: O(N)
| test | time | result |
|---|---|---|
| example Test from the task description | 0.100 s. | OK |
| simple | 0.090 s. | OK |
| extreme_large_numbers Sequence with extremly large numbers testing arithmetic overflow. | 0.070 s. | RUNTIME ERROR tested program terminated unexpectedly stdout: Unhandled Exception: System.OverflowException: Number overflow. at System.Linq.Enumerable. |
| overflow_tests | 0.070 s. | RUNTIME ERROR tested program terminated unexpectedly stdout: Unhandled Exception: System.OverflowException: Number overflow. at System.Linq.Enumerable. |
| one_large one large number at the end of the sequence | 0.070 s. | OK |
| sum_0 sequence with sum=0 | 0.080 s. | OK |
| single single number | 0.070 s. | OK |
| empty Empty array | 0.060 s. | OK |
| combinations_of_two multiple runs, all combinations of {-1,0,1}^2 | 0.070 s. | OK |
| combinations_of_three multiple runs, all combinations of {-1,0,1}^3 | 0.070 s. | OK |
| small_pyramid | 0.070 s. | OK |
| large_long_sequence_of_ones | 0.100 s. | OK |
| large_long_sequence_of_minus_ones | 0.120 s. | OK |
| medium_pyramid | 0.090 s. | OK |
| large_pyramid Large performance test, O(n^2) solutions should fail. | 0.160 s. | OK |