Java0715/lesson/src/com/sf/leetcode/Solution_LCR012.java

package com.sf.leetcode;

public class Solution_LCR012 {

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

    // [1,7, 3, 6, 5, 6]
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        // 计算总和
        int total = 0;
        for (int i = 0; i < n; i++) {
            total += nums[i];
        }
        // total = 28

        // 计算元素的前缀和 是否符合要求
        int sum = 0;
        for (int i = 0; i < n; i++) {
            //  0 1 8 11 17 22 28
            // 后面元素之和 = 所有元素之和 - 自身 - 前面元素之和
            // 11 = 28 - 6 - 11
            if (sum == total - nums[i] - sum) {
                return i;
            }
            sum += nums[i];
        }
        // 找不到符合条件的索引
        return -1;
    }

    // 使用正序和 和 逆序和 计算
    public int pivotIndex1(int[] nums) {
        int n = nums.length;
        int[] sort = new int[n + 1];
        int[] reSort = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            // sort[1] = sort[0] + nums[0]
            sort[i] = sort[i - 1] + nums[i - 1];
        }
        int index = -1;
        if (reSort[n - 1] == sort[n - 1]) {
            index = n - 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            // reSort[n-2] = reSort[n-1] + nums[n-1];
            reSort[i] = reSort[i + 1] + nums[i + 1];
            if (reSort[i] == sort[i]) {
                index = i;
            }
        }


//        for (int i = 0; i < n; i++) {
//            if (sort[i] == reSort[i]) {
//                return i;
//            }
//        }

        return index;
    }

}