Shulou(Shulou.com)06/02 Report--

This article introduces Python how to find the central index, the content is very detailed, interested friends can refer to, I hope it can be helpful to you.

1 topic

Given an array nums of integer type, write a method that returns the array's "central index".

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

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

Example 1:

Input: nums = [1,7,3,6,5,6] output: 3 explanation: the sum of the left number of index 3 (nums [3] = 6) (1 + 7 + 3 = 11) is equal to the sum of the right number (5 + 6 = 11). At the same time, 3 is the first central index that meets the requirements. Example 2:

Input: nums = [1,2,3] output:-1 explanation: there is no central index in the array that satisfies this condition. Please complete the following code:

Class Solution:

Def pivotIndex (self, nums: List [int])-> int:

2 comparison of two solutions

Refer to the analysis and code of Xingyou infrared62*:

This solution is very efficient.

Summary of infrared62*: the application of Java and Python, prefix sum, prefix sum can be simply regarded as the sum of the first n terms of a sequence, and it is also used in DP and tree path summation, as well as suffix sum, prefix product, suffix product.

However, I also see that some stars solve the problem like this:

Compared with the first method, this method is not efficient.

Because each iteration requires sum summation twice, and sum summation is essentially a loop, it is equivalent to a nested for loop.

We need to think about whether it is necessary to make peace every time, which is obviously not necessary.

If there is a central index, it must satisfy: left side of the central index and * 2 + nums [I] = = sum (nums)

While sum (nums) must be a fixed value, the left summation of the central index can be gradually accumulated in a loop, so only one layer of for can be used.

3 Analysis and summary

Often, the solution we think of in the first place may not be the most efficient, and we need to do more analysis to cultivate algorithmic thinking. If you want to cultivate algorithmic thinking and sharpness, you need to practice more. It is usually a good way to train LeetCode questions back and forth.

The result after training, just like the above star friend infrared62*, saw this problem and immediately thought of a series of similar ideas: prefix sum can be simply regarded as the sum of the first n terms of the sequence, and it can also be used in DP and tree path summation, as well as suffix sum, prefix product, suffix product.

About Python how to find the central index to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.