现在给你两个长度均为 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

大佬有話說 (0)