现在给你两个长度均为 N 的整数数组 A 和 B 。
当(A[0]+...A[K-1])，(A[K]+...+A[N-1])，(B[0]+...+B[K-1]) 和 (B[K]+...+B[N-1])四个和值大小相等时，称索引 K 是一个公平索引。也就是说，索引 K 可以使得 A，B 两个数组被分成两个非空数组，这四个子数组的和值相等。
例如，数组 A = [4,-1,0,3]，B = [-2,5,0,3]，那么索引 K = 2 是公平的，子数组的和相等：4+(-1) = 3; 0+3 = 3; -2 + 5 = 3 and 0 + 3 = 3 。
现在请你计算公平索引的个数。 2<=N<=100000 -1000000000<=a[i],b[i]<=1000000000 (0<=i<N)
在线评测地址： https://www.lintcode.com/problem/fair-indexes/?utm_source=sc-v2ex-fks
样例 1: 输入: [4,-1,0,3] [-2,5,0,3] 输出: 2
样例 2: 输入: [2,-2,-3,3] [0,0,4,-4] 输出: 1
样例 3: 输入: [4,-1,0,3] [-2,6,0,4] 输出: 0
样例 4: 输入: [1,4,2,-2,5] [7,-2,-2,2,5] 输出: 2
[题解]
先判断两个数组总和是否相等，若不相等，则直接返回 0 ； 然后扫一遍数组，用 pre_a 和 pre_b 分别记录两个数组的前缀和，前缀和相等时 ans++即可。
需要注意的是，数组中数的值在-1e9,1e9 范围内，数组长度 0，1e5，所以中间和会超出 int 范围，需要用 long ；
还有被分成的两个数组不能为空，所以前缀和 p0 和 pn-1 是不考虑的； public class Solution { /** * @param A: an array of integers * @param B: an array of integers * @return: return a integer indicating the number of fair indexes. */ public int CountIndexes(List<Integer> A, List<Integer> B) { int ans = 0; long sum_a = 0, sum_b = 0, pre_a = 0, pre_b = 0; for(int i = 0; i < A.size(); i++) { sum_a += A.get(i); sum_b += B.get(i); } if(sum_a != sum_b)return 0; for(int i = 0; i < A.size() - 1; i++) { pre_a += A.get(i); pre_b += B.get(i); if(pre_a==pre_b) ans++; } return ans; } }
更多语言代码参见： https://www.jiuzhang.com/solution/fair-indexes/?utm_source=sc-v2ex-fks