讨论/《数组和字符串》 - 寻找数组的中心索引/
《数组和字符串》 - 寻找数组的中心索引
共 125 个回复

为了节约时间,需要考虑左求和*2+nums[i]=总和

34

第一题就卡壳了,我觉得我不配学DS了T_T

30

Java:执行用时1ms,在所有Java提交中击败了100.00%的用户
内存消耗:38.7MB,在所有Java提交中击败了97.86%的用户
运行前请删除注释,否则会影响运行时间和文件大小,谢谢

class Solution {
    public int pivotIndex(int[] nums) {
        int sum=0,flag=0,end=0;
        for(int i=0;i<nums.length;i++){//sum为数组中所有元素的总和
            sum+=nums[i];
        }
        if(sum-nums[0]==0){//如果除了nums[0]以外的和为0,即0为数组的中心索引
            return 0;
        }
        for(int j=0;j<nums.length;j++){//flag为数组中从索引为0的位置到索引为j的位置的所有元素的和
            flag+=nums[j];
            if(j!=0){
                end=flag-nums[j];//end为数组中从索引为0的位置到索引为j-1的位置的所有元素的和
            }
            while(end==sum-flag){//数组中索引为j的位置前的所有元素总和
                                //与数组中索引位置为j的位置后的所有元素总和相等
                return j;
            }
        }
        return -1;
    }
}
24

C++

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        if(nums.empty())
            return -1;
        int left_sum=0,right_sum=accumulate(nums.begin(), nums.end(), 0);
        for(int i=0;i<nums.size();++i)
        {
            left_sum+=nums[i];
            if(i>0)
                right_sum-=nums[i-1];
            if(left_sum==right_sum)
                return i;
        }
        return -1;
    }
};
10

python,思路简单:
先计算总和,然后遍历计算left总和,如果left总和×2加当前值等于总和,就返回当前值~

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        all = sum(nums)
        left = 0
        for i in range(len(nums)):
            if left * 2 + nums[i] == all:
                return i
            else:
                left += nums[i]
        return -1
8

这个是不是有什么问题,预期是 0也就是数组第一个数,其左边都没有数据,怎么就能等于右边数之和?
image.png

7
class Solution {
     public static int pivotIndex(int[] nums) {
    	if( nums.length == 0)
            return -1;
        
        int leftSum = 0, rightSum = 0;
        
        for( int i = 1; i < nums.length ; i++)
            rightSum += nums[i];
        
        if( leftSum == rightSum)
            return 0;
        
        for( int i = 1; i < nums.length ; i++){
            rightSum -= nums[i];
            leftSum += nums[i - 1];
            if( rightSum == leftSum)
                return i;
        }
        
        return -1;
    }
}
6

将sumleft和sumright都算上当前元素的值就不需要考虑特殊情况当j=0的时候了,对于只有一个元素或者没有元素的数组也适用
c++

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sumleft = 0, sumright = 0;
        for (auto i : nums) {
            sumright += i;
        }
        for (int j = 0; j < nums.size(); j++) {
            sumleft += nums[j];
            if (sumleft == sumright) return j;
            sumright -= nums[j];
        }
        return -1;
    }
};
4
var pivotIndex = function (nums) {
    let sumL = 0,
        sumR = 0;
    // 求数组总和
    for (let item of nums) {
        sumR += item
    }
    // 如果 sumL 和 sumR 减去当前值之后的结果相等,就返回该下标
    // 否则 sumL 加上当前值,指针右移
    for (let i = 0; i < nums.length; i++) {
        if (sumL === (sumR -= nums[i])) return i
        sumL += nums[i]
    }
    return -1
};
3

后续题目也尽量抛弃循环嵌套,容易超时。
Python3 :计算总量然后逐步减去左边和.

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        index = len(nums)
        numsSum = sum(nums)
        leftSum = 0
        for i in range(index):
            if leftSum == numsSum - leftSum - nums[i]:
                return i
            leftSum += nums[i]
        return -1
2