724. 寻找数组的中心下标

1、题目描述

2、解决方法

2-1、暴力法 

        顺着题目思路走，遍历每个下标，分别计算下标左边的汇总和和下标右边的汇总和，这个想法很好理解，没有任何技巧。需要注意的就是涉及到边界情况：

边界情况1:  数组为null, 则不存在这样的下标，返回-1；

边界情况2:  存在数组元素，且元素个数有且就是1个，这样想想自然这个元素左边和右边都没有数据，左边汇总和=右边汇总和=0，返回下标0；

边界情况3: 存在数组元素，且目标下标在边界处，特殊处理：

if(nums.length > 1 && getSum(nums,l+1,r) == 0){
      return l;
}

最后进行全遍历，这个逻辑说实话在自测的时候，经常有case异常，因此后续追加了几次边界情况，完全不推荐！完整代码如下：

class Solution {
    public int pivotIndex(int[] nums) {
      if(nums==null || nums.length == 0) return -1;
      if(nums.length == 1 ) return 0;
      
      int l = 0; int r = nums.length-1;
      //初始化模式
      if(nums.length > 1 && getSum(nums,l+1,r) == 0){
           return l;
      }
      for(int i = 1; i < nums.length; i++){
           int sum1 = getSum(nums, l, i-1);
           int sum2 = getSum(nums,i+1,r);
           if(sum1 ==sum2)
               return i;
      }
      return -1;
    }
 
    private int getSum(int[] nums, int start, int end){
       int sum = 0;
       for(int i = start; i<= end; i++){
           sum += nums[i];
       }
       return sum;
    }
}

复杂度分析

• 时间复杂度：O(n^2)，其中 n 为数组的长度。

• 空间复杂度：O(1)。

备注：很不推荐，容易缺失边界情况，时间复杂度还高。

2-2、求和法（推荐）

这个思路是看官方解题思路，相对简单很多，还不用考虑多种边界特殊情况，解决方法也相对简单很多，思路很巧妙。

【备注】可以使用现成的求和方法：int total = Arrays.stream(nums).sum();

1、求和获取 total.

2、两边的汇总和，设置为2*sum

3、存在恒等式，2*sum+nums[i] = total; 

此时也无需考虑多种特殊边界情况，这种逻辑所有情况均满足。完整代码如下：

class Solution {
    public int pivotIndex(int[] nums) {
       int total = Arrays.stream(nums).sum();
       int sum = 0;
       for(int i = 0; i< nums.length; i++){
           if(2 * sum +nums[i]==total)
                return i;
           sum += nums[i];
       } 
       return -1;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组的长度。

• 空间复杂度：O(1)。