LeetCode 剑指 Offer 66. 构建乘积数组

Categories:

题目描述
思路分析
1. 解法一：前后缀乘积（推荐）
相似题目

题目描述

✅ 剑指 Offer 66. 构建乘积数组

思路分析

解法一：前后缀乘积（推荐）

核心思路：

先计算每个位置左侧元素的乘积。

再从右侧累乘，乘到左侧积上得到结果。

不使用除法，满足题意。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)，不计输出数组。

class Solution {
    public int[] constructArr(int[] a) {
        if (a.length == 0) {
            return new int[0];
        }

        int n = a.length;
        int[] res = new int[n];
        res[0] = 1;

        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] * a[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] = res[i] * right;
            right *= a[i];
        }

        return res;
    }
}

func constructArr(a []int) []int {
	if len(a) == 0 {
		return []int{}
	}

	n := len(a)
	res := make([]int, n)
	res[0] = 1

	for i := 1; i < n; i++ {
		res[i] = res[i-1] * a[i-1]
	}

	right := 1
	for i := n - 1; i >= 0; i-- {
		res[i] = res[i] * right
		right *= a[i]
	}

	return res
}

相似题目

题目	难度	考察点
238. 除自身以外数组的乘积	中等	前后缀
724. 寻找数组的中心下标	简单	前缀和
303. 区域和检索 - 数组不可变	简单	前缀和
42. 接雨水	困难	双指针
189. 轮转数组	中等	数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/15472452