Произведение чисел массива за исключением элемента в индексе i

Источник: https://leetcode.com/problems/product-of-array-except-self/

Дан массив целых чисел nums, подсчитать массив answer такой, чтоanswer[i] равен произведению всех элементов из nums за исключением nums[i].

Алгоритм должен быть линейным и не должен содержать операций деления.

Пример 1:

Дано: nums = [1,2,3,4]
Результат: [24,12,8,6]

Пример 2:

Дано: nums = [-1,1,0,-3,3]
Результат: [0,0,9,0,0]

Ограничения:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• Произведение любого суффикса или префикса массива nums гарантированно помещается в целое 32-битное число.

Идея решения

Мы можем итеративно подсчитвать произведение всех элементов слева от индекса i, продвигаясь по i от 0 до n (длинна массива). И запоминать в массиве L длинной n промежуточное произведение.

Затем мы сканируем массив в обратном направлении от n до 0, и считаем произведение всех элементов слева от индекса i. Эти значения мы можем тоже запомнить во временном массиве R.

L[i]*R[i] даст искомый результат для каждого индекса i.

Сложность линейная. Операций деления нет.

Мы можем сэкономить память на массиве R и считать промежуточное произведение элементов справа в переменной, которая аккумулируется по мере сканирования массива справа налево. Это промежуточное значение мы тут же умножаем на L[i], и тогда массив L будет содержать искомые значения.

Имплементация

class Solution {
    public int[] productExceptSelf(int[] nums) {

        // Длинна исходного массива
        int length = nums.length;

        // Результат, который мы вернем
        int[] answer = new int[length]; // массив L

        // answer[i] содердит произведение всех элементов слева от i
        // Для элемента в индексе 0 нет элементов слева, поэтому:
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            // answer[i - 1] содержит произведение элементов слева от 'i - 1'
            // Поэтому просто умножим на nums[i - 1]:
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // Пусть переменная R состоит из произведения всех элементов справа
        // инициализируем:
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {

            // На индексе 'i',
            // R будет содержать произведение всех элементов справа от i.
            // answer[i] содержит все элементы слева от i.
            // Тогда умножив answer[i] на R мы получим произведение всех
            // элементов массива за исключением элемента в i
            answer[i] = answer[i] * R; // прозведение кроме i
            // продолжаем увеличивать R
            R *= nums[i];
        }

        return answer;
    }
}