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

This article mainly introduces LeetCode how to solve the problem of array center index, the article is very detailed, has a certain reference value, interested friends must read it!

Topic description:

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

Central index: 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 side.

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:

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 also the first central index input that meets the requirements: nums = [1,2,3] output:-1 explanation: there is no central index in the array that meets this condition.

Description:

The length range of nums is [0, 10000]

Any nums [I] will be an integer in the range of [- 1000, 1000]

The first attempt

Idea: use an index label to move from the array header and set the left_nums and right_nums parameters to calculate the left and right sum

Note:

Left_nums and right_nums are in the loop, because each time you reset

There may be negative numbers in the array, so there may also be the first element or the last element is the central index

Running result:

Because there are too many cycles, the time efficiency is low.

This article is supported by "one partner Editor".

First optimization

Reduce loops: flexible use of array slices

The memory parameters and space consumption are reduced, but the time efficiency is still low.

This article is supported by "one partner Editor".

Final optimization method

Idea: if index is the central index, then left and = right sum, so you can introduce a formula:

S (sum of arrays) = left_nums (left and) * 2 + nums [index]

So you only need to dynamically calculate the left and left_nums (another parameter is reduced)

Dynamic calculation: first determine whether it is the central index, then move the index, and calculate the left side and left_nums

Special phenomenon: the movement of the left side and the left_nums and the index label is synchronized. When the index label moves one bit to the right, the left_nums will add the corresponding value of the previous index.

These are all the contents of the article "how LeetCode solves the problem of indexing in the center of an array". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.