题目:
给你一个下标从 0 开始的整数数组 nums
,请你找到 最左边 的中间位置 middleIndex
(也就是所有可能中间位置下标最小的一个)。
中间位置 middleIndex
是满足 nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1]
的数组下标。
如果 middleIndex == 0
,左边部分的和定义为 0
。类似的,如果 middleIndex == nums.length - 1
,右边部分的和定义为 0
。
请你返回满足上述条件 最左边 的 middleIndex
,如果不存在这样的中间位置,请你返回 -1
。
解法一:
求下标i之前的元素和以及下标i之后的元素和,再将两两比较,如果相等,则返回i,如果无法匹配,则1返回-1;
class Solution {
public int findMiddleIndex(int[ ] nums){
for (int i = 0; i < nums.length; i++){
int before = beforeSum(nums, i);
int after = afterSum(nums, i);
if (before == after ){
return i;
}
}
return -1;
}
public int beforeSum(int [ ] nums, index){
int sum = 0;
for(int i =0; i < index; I++){
sum += nums[i];
}
return sum;
}
public int afterSum(int [ ] nums, index){
int sum = 0;
for(int i = index + 1; i < nums.length; i++){
sum += nums[i];
}
return sum;
}
}
解法二:
前缀和 + nums[i] + 后缀和 = 总和 ,所以 2*前缀和 = 总和 - nums[i]。
public int findMiddleIndex(int [ ] nums){
int sum = 0;
for (int num : nums) {
sum += num;
}
int preSum = 0;
for (int i = 0; i < nums.length; i++){
if (preSum * 2 == Sum - nums[i])
return i;
}
preSum += num[i];
}
return -1;
}