寻找数组的中心索引
程序员文章站
2022-07-13 17:31:08
...
平时写项目时,碰到算法相关问题,都要思考许久,所以从现在开始坚持学习算法,从易到难!主要目的学习算法的思路!今天看下怎么寻找一个数组的中心索引,看下面示例示例 1:
输入:
nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11),与右侧数之和 (5 + 6 = 11) 相等。
同时, 3 也是第一个符合要求的中心索引。
示例 2:
输入:
nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心索引。
我以为只能从排除第一项和最后项的位置去找中心索引位置,看到上面的结果我错了,中心索引位置也可以是第一项和最后项!所以我的思路(还是很繁琐),一开始在数组的头和尾加上两个0,然后排除空数组的情况(只有我加的2个0),然后一个从左边开始算,一个从右边开始算,左边等于右边输出索引!
/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function(nums) {
let left = right = 0;
nums.push(left);
nums.unshift(right);
if (nums.length == 2) {
return -1;
};
for (let i = 0; i < nums.length - 2; i++) {
left = nums[i] + left;
for (let k = nums.length - 1; k > i + 1; k--) {
right = nums[k] + right;
}
if (left == right) {
return i;
} else {
right = 0;
}
}
return -1;
};
这个方法毕竟还是很复杂,多次判断和多次循环!然后再想了下别的方法!假如一个数组arr,leftNumber+leftNumber+arr[i]=arr总和,思路是数组左边+数组右边+中间索引位置的值 =数组总和!这个方法代码量也很少!判断也少!
/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function(nums) {
let totolNumber = nums.reduce(function (a, b) {
return a + b;
}, 0);
let leftNumber = 0;
for (var i = 0; i < nums.length; i++) {
if (totolNumber - nums[i] === 2 * leftNumber) {
return i;
}
leftNumber += nums[i];
}
return -1;
};
上一篇: 724.寻找数组的中心索引