【算法】寻找数组中心下标 - 双指针/求总和

题目

给定一个非空数组，找到一个元素，该元素左侧元素和等于其右侧元素和，返回该元素下标。
如果没有则返回-1，有多个则返回最左侧一个。

原理

1、双指针

定义两个变量，一个为从左侧累加的和 leftSum = 0，一个从右侧递减的和 rightSum，rightSum初始值为整个数组的和。
遍历数组，每次遍历先让 leftSum + 当前元素，此时两个Sum都包含当前元素，如果两个Sum相等，则当前元素为中心元素；否则让 rightSum 减去当前元素，如此循环即可。

2、求总和

定义两个变量，一个 sum = 0，一个 arraySum，初始化为整个数组的和。
遍历数组，当 sum * 2 + 当前元素 = arraySum时，当前元素即为中心元素，不想等则让 sum 加上当前元素。因为中心元素两侧的和相等，即两侧的和实际为 sum * 2。

代码

1、双指针

    public static void main(String[] args) {
        System.out.println(findCenterIndex(new int[]{1, 7, 3, 6, 5, 6}));
    }

    public static int findCenterIndex(int[] nums) {
        int rightSum = Arrays.stream(nums).sum();
        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            leftSum += nums[i];
            if (leftSum == rightSum) {
                return i;
            }
            rightSum -= nums[i];
        }
        return -1;
    }

2、求总和

    public static void main(String[] args) {
        System.out.println(findCenterIndex2(new int[]{1, 7, 3, 6, 5, 6}));
    }

    public static int findCenterIndex2(int[] nums) {
        int arraySum = Arrays.stream(nums).sum();
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum * 2 + nums[i] == arraySum) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }