一 🏠 题目描述
剑指 Offer 66. 构建乘积数组
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5] 输出: [120,60,40,30,24]
提示：
所有元素乘积之和不会溢出 32 位整数
a.length <=100000
二 🏠破题思路
2.1 🚀 关键信息
解决问题第一步，当然先提取题目字面上的关键信息 😎😎😎
题干简直超易理解，数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]
看到这句的时候，各位看官大大应该和博主一样已经笑开了 🌸🌸🌸 吧
但是这道题的核心点是 不能使用除法 😖😖😖
提取完题目中的关键信息后，直接进入第二阶段，思路整理 😃😃😃
2.2 🚀 思路整理
如 2.1 所述，该题难点在于不能使用除法，即 只用乘法 生成数组 B
根据题目对 B[i] 的定义，可列表格，如下图所示
根据表格的主对角线（全为 1 ），可将表格分为 上三角 和 下三角 两部分；分别迭代计算下三角和上三角两部分的乘积，即可 不使用除法 就获得结果
三 🏠 代码详解
3.1 🚀 代码实现
按照我们刚才的破题思路，直接代码走起来 👇👇👇👇
std::vector<int> constructArr(std::vector<int>& a) { int len = a.size(); //输入数组长度 std::vector<int> b(len, 1); //初始化输出数组 b int left =1, right =1; //初始化左右双指针 for (int i =0; i < len; ++i) { //遍历输入数组 b[i] *= left; //left = 索引i位置左边所有数乘积, *= 赋值给 b[i] left *= a[i]; //索引i位置左边所有数乘积 * a[i] b[len -1- i] *= right; //right = 索引len-1-i位置右边所有数乘积, *= 赋值给 b[len-1-i] right *= a[len -1- i]; //索引len-1-i位置右边所有数乘积* a[len -1- i] } return b; }
3.2 🚀 细节解析
看完 👀👀👀 全注释版的代码实现后，相信看官大大对整体逻辑已经是大写的 OK 了 😃😃😃
那么我们挖掘上述实现的晦涩细节 😖😖😖 进行解析，直接开干，走起来 👇👇👇👇
b[i] *= left; //left = 索引i位置左边所有数乘积, *= 赋值给 b[i] left *= a[i]; //索引i位置左边所有数乘积 * a[i]
left 是索引 i 位置左边所有数乘积，*= 就是在把索引 i 位置左边所有数乘积赋值给 b[i]
left *= a[i] 为了一下循环（++i）提前计算 i 位置左边所有数乘积
那么这个过程就对应了，2.2 图示中的正三角过程（右部分的倒三角逻辑同理） 🌹🌹🌹
当然也可以使用两次循环，将正倒三角各元素乘积分开计算，在逻辑上或许会更好理解。但却多了一次遍历的开销，这里使用了双指针的操作（凡是等效逻辑正逆向遍历两次，均可使其简化为一次完成） 😜😜😜
四 🏠 心路历程
为方便各位看官大大了解博主真实刷题过程，我把当时状态纯纯真实还原，记录在心路历程这一小节，不感兴趣的小伙伴可以直接跳过哈
博主在第一阶段提取 🚀 关键信息并没有问题，在第二阶段 🚀 思路整理中有考虑尝试使用双指针，但是未联想到 上三角 和 下三角（破题关键点）😭😭😭
所以博主的这道题是在阅读完官方解析后，解出来并加以记录的
