Leetcode 724: find the central index of the array (java, python3)

Find the central index of an array

Given an array nums of integer type, write a method that can return the "central index" of the array.

We define the array central index as follows: the sum of all elements on the left side of the array central index is equal to the sum of all elements on the right side.

If the array does not have a central index, then we should return - 1. If the array has more than one central index, we should return the one closest to the left.

Example 1:

Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
 Interpretation: 
The sum of the numbers on the left side of index 3 (nums[3] = 6) (1 + 7 + 3 = 11) is equal to the sum of the numbers on the right side (5 + 6 = 11).
At the same time, 3 is the first qualified central index.

Example 2:

Input: 
nums = [1, 2, 3]
Output: -1
 Interpretation: 
There is no central index in the array that satisfies this condition.

Explain:

  • The length range of nums is [0, 10000].
  • Any nums[i] will be an integer in the range of [- 1000, 1000].

At first, my idea is to judge whether I want to wait from the left and right accumulation of the first index:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        int sumLeft=0,sumRight=0;
        Scanner scan =new Scanner(System.in);
        while (scan.hasNextInt()){
            nums.add(scan.nextInt());
        }
        int numsSize=nums.size()-1;
        for(int i=1;i<numsSize;i++){
            for(int j=0;j<i;j++){
                sumLeft+=nums.get(j);
            }
            for(int j=numsSize;j>i;j--){
                sumRight+=nums.get(j);
            }
            if(sumLeft==sumRight){
                System.out.println(i);
                break;
            }else {
                sumLeft=sumRight=0;
            }
        }
        if(sumLeft==0){
            System.out.println(-1);
        }
    }
}

After that, search for other people's answers... As expected, he was hanged.

Solutions:

Reference blog Park

Left accumulation does not need to start from index 0, the previous accumulation plus the next index. The right accumulation can be calculated by subtracting the left accumulation from the sum once.

Reference resources: Judge central index conditions

Left index if equal to right, i.e. double left cumulative sum + center index = sum

java:

class Solution {
    public int pivotIndex(int[] nums) {
       int sumLeft=0,sum=0;
        for (int n:nums){
            sum = sum + n;
        }
        int numsSize=nums.length-1;
        for(int i=0;i<=numsSize;i++){
            if(i==0){
                sumLeft=0;
            }else{
                sumLeft+=nums[i-1];
            }
            //Left index if equal to right, double left plus center index = sum
            if(sumLeft*2+nums[i]==sum){
                return i;
            }
        }
       return -1;
    }
}

In particular, the index must start from 0 to the last one, because the sum of the right side of the central index after the title can be 0.

In the java default template, int[] nums refers to the input of int array from the console. There is no need for Arraylist to dynamically construct the array.

python3

nums is a list dynamic array

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        """
        :type nums: int
        """
        sumAll=sum(nums)
        leftSum=0
        for i in range(len(nums)):
            if(i==0):
                leftSum=0
            else:
                leftSum+=nums[i-1]
            #Left index if equal to right, double left center index = sum
            if(leftSum*2+nums[i]==sumAll):
                return i
        return -1

Tags: Java

Posted on Sun, 03 Nov 2019 01:23:19 -0700 by jeremyhowell