You are going to be given an array of integers. Your job is to take that array and find an index N where the sum of the integers to the left of N is equal to the sum of the integers to the right of N. If there is no index that would make this happen, return -1
.
题目意思是在给定数组中找出一个位置,该位置左边部分整数的和和右边部分整数的和相等。如果该位置不存在,返回-1
思路就是遍历整个数组,每次求左右部分的和,比较是否相等,如果相等,就返回该位置。show code:
function findEvenIndex(arr) { var arr1,arr2,font,end; for(var i=0;i<arr.length;i++){ font=0; end=0; arr1=arr.slice(0,i); arr2=arr.slice(i+1); for(var j=0;j<arr1.length;j++){ font+=arr1[j]; } //左边和 for(var k=0;k<arr2.length;k++){ end+=arr2[k]; } //右边和 if(font==end){ return i; break; //找到后跳出循环 } } return -1; }
做完后想想如果存在多个这样的位置呢,可以把符合条件的所有位置找出来。代码稍微改变下就ok了
function findEvenIndex(arr) { var flag=[]; var arr1,arr2,font,end; for(var i=0;i<arr.length;i++){ font=0; end=0; arr1=arr.slice(0,i); arr2=arr.slice(i+1); for(var j=0;j<arr1.length;j++){ font+=arr1[j]; } for(var k=0;k<arr2.length;k++){ end+=arr2[k]; } if(font==end){ flag.push(i); } } if(flag.length==0){ return -1; } else{ return flag; } }
就是把所有符合条件的位置存在数组中最后返回。
最后推荐一个时间复杂度为O(n)的算法:
function findEvenIndex(arr) { var sum = arr.reduce((a,b) => a+b); var l=0; for(var i=0;i<arr.length;i++){ sum-=arr[i]; if(l==sum){ return i; } l+=arr[i]; } return -1; }