День-13 Найти индекс с поворотом

Задний план

Это заявление о проблеме является частью массивов и строк и струн обучения LeetCode. Под подзаголовкой введение в массив.

Постановка задачи

Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Примечание:

1. Длина номеров будет в диапазоне [0, 10000].
2. Каждый элемент nums [i] будет целым числом в диапазоне [-1000, 1000].

Решение подход 1.

1. Чтение проблемы задачи Интуитивно понятный метод, который ударил, должен был нарезать список. И продолжать расчет суммы этих нарезанных подписи. Когда сумма элементов на левую сторону элемента и правой стороны элемента совпадает. Вернуть индекс.

Проблемы с подходом 1

1. Это приведет к неоптимизированному решению. Нарезка имеет своевременную сложность в зависимости от длины сублиста. Общая сложность стала бы квадратичной.

Решение подход 2

1. Возьмите ручку и бумагу и математически старайтесь наблюдать за рисунком.
2. Рассчитайте все элементы, присутствующие в списке.
3. Затем вычислите сумму всех элементов на левую сторону текущего индекса. Храните эту сумму для каждого элемента в новом списке.
4. Сумма правой стороны будет. – Значение элемента в текущем индексе – сумма левых сторон элементов при одном индексе.

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = 0
        result = -1
        for x in range(0, len(nums)):
            total += nums[x]

        element_sum = 0
        left_side_sum = [0] # Sum of elements to the left of value
        for i in range(1, len(nums)):
            element_sum += nums[i-1]
            left_side_sum.append(element_sum)

        for index in range(0, len(nums)):
            right_side_sum = total - nums[index] - left_side_sum[index]
            if right_side_sum == left_side_sum[index]:
                result = index
                break

        return result

Учащиеся и вынос

1. Сложность времени – O (n), космическая сложность – O (n)
2. Сложность времени Append – O (1)
3. Первый элемент flal_side_sum инициализируется до 0, потому что в списке нет значения левой стороны левого элемента.

Оригинал: “https://dev.to/mridubhatnagar/day-13-find-pivot-index-27lh”