首页 > 代码库 > 【HackerRank】Sherlock and Array
【HackerRank】Sherlock and Array
Watson gives an array A1,A2...AN to Sherlock. Then he asks him to find if there exists an element in the array, such that, the sum of elements on its left is equal to the sum of elements on its right. If there are no elements to left/right, then sum is considered to be zero.
Formally, find an i, such that, A1+A2...Ai-1 = Ai+1+Ai+2...AN.
Input Format
The first line contains T, the number of test cases. For each test case, the first line contains N, the number of elements in the array A. The second line for each testcase contains N space separated integers, denoting the array A.
Output Format
For each test case, print YES if there exists an element in the array, such that, the sum of elements on its left is equal to the sum of elements on its right, else print NO.
Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 105
1 ≤ Ai ≤ 2*104 for 1 ≤ i ≤ N
先求出数组总的sum，然后遍历一遍数组，遍历的过程中分别累加（减）求出一个元素的左边元素之和left（left的累加在这个元素上一个元素的循环中完成，见代码第30行）和右边元素之和right，然后比较是否相等即可，时间复杂度O(n)，代码如下：
1 import java.io.*; 2 import java.util.*; 3 import java.text.*; 4 import java.math.*; 5 import java.util.regex.*; 6 7 public class Solution { 8 public static void main(String[] args) { 9 Scanner in = new Scanner(System.in);10 int t = in.nextInt();11 while(t-- > 0){12 int n = in.nextInt();13 int[] num = new int[n];14 int sum = 0;15 16 for(int i = 0;i < n;i++){17 num[i] = in.nextInt();18 sum += num[i];19 }20 int left = 0;21 int right = sum;22 boolean find = false;23 for(int i = 0;i < n;i++){24 right -= num[i];25 if(left == right)26 {27 find = true;28 break;29 }30 left += num[i];31 }32 if(find)33 System.out.println("YES");34 else35 System.out.println("NO");36 }37 }38 }