寻找数组的中心索引

寻找数组的中心索引 724题

我的思路：遍历数组中每一位，计算这一位左边的和leftSum和右边的和rightSum。

class Solution {
    public int pivotIndex(int[] nums) {
        int leftSum=0;
        int rightSum=0;
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<i;j++){
                       leftSum=leftSum+nums[j];
               
            }
            for(int k=i+1;k<nums.length;k++){
                      rightSum=rightSum+nums[k]; 
            }
             System.out.println(leftSum);
            if(rightSum==leftSum){
                return i;
            }else {
                leftSum=0;
                rightSum=0;
            }
        }return -1;
    }
}

时间复杂度拉满。。。。。。。

相同的思路另一种解决方法：先求rightSum，在遍历数组第i位时，rightSum减去i位的值，leftSum加上i-1位的值，然后进行比较

class Solution {
    public int pivotIndex(int[] nums) {
        if(nums.length==0)return -1;
        int leftSum=0;
        int rightSum=0;
        for(int i=1;i<nums.length;i++){//注意此处从1开始，因为在比较时右侧的和永远把第一位计算在内
          rightSum=rightSum+nums[i];
        }
        if(rightSum==leftSum) return 0;
       
       for(int i=1;i<nums.length;i++){
          rightSum=rightSum-nums[i];
           leftSum=leftSum+nums[i-1];
           System.out.println("l"+leftSum);
            System.out.println("r"+rightSum);
           if(rightSum==leftSum) return i;
        }
        return -1;
    }
}

另一种采用数学的巧妙的方式

rightSum+leftSum+nums[i]=sum//右侧的和+左侧的和+当前索引对应的值=数组中所有数的总和
rightSum=leftSum时
2*leftSum+nums[i]=sum//以此作为判断条件也可以减少时间复杂度

class Solution {
    public int pivotIndex(int[] nums) {
        if(nums.length==0)return -1;
        int leftSum=0;
        int rightSum=0;
        int Sum=0;
        for(int i=0;i<nums.length;i++){
         Sum=Sum+nums[i];
        }
         for(int i=0;i<nums.length;i++){
           
             if(2*leftSum+nums[i]==Sum)
                 return i;
              leftSum=leftSum+nums[i];
        }
        return -1;
    }
}