寻找数组的中心索引

发表于
本文字数： 698 阅读时长 ≈ 1 分钟

LeetCode每日一题，742. Find Pivot Index

先看题目描述

ySB4XD.png

大意就是给定一个数组 nums，让我们求它的中心索引并返回，中心索引的定义是左边的元素之和等于右边的元素之和

算法和思路

前缀和

使用前缀和，然后遍历数组即可

设数组的所有元素之和为 sum，遍历到第 i 个元素时，设其左边元素之和为 cur，要判断其左边元素之和是否与右边元素之和相等，只需比较 cur 与 sum - cur - nums[i] 即可，即 2 * cur + nums[i] 是否等于 sum

算法源码

前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int pivotIndex(int[] nums) {
        int len = nums.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }
        int cur = 0;
        for (int i = 0; i < len; i++) {
            if (2 * cur + nums[i] == sum) {
                return i;
            }
            cur += nums[i];
        }
        return -1;
    }
}