大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位刚毕业没多久的字节员工发帖求助，他说工作上一直要求成长和思考，一直被否定，已经分不清是自身的问题还是字节的问题了。
评论区的职场老鸟都纷纷开导他，有人认为他需要尽快转变这种靠别人的认可才觉得有价值的学生思维，不然很容易被人利用，工作价值是没办法被精确量化的，绩效评定只是管理的工具，大部分时候全凭个人观感，绩效好的更像是被推出来给其他人学习的榜样，这就是管理的价值导向。还有人认为工作的目的是赚钱，平时要多积累对自己跳槽有帮助的事，任何工作都是过客，不要太在意。甚至有些人教他要多拍马屁，多表忠心，好活去抢，烂活远离。不得不说句句都是深刻的职场感悟。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道字节的面试原题「除自身以外数组的乘积」。
题目描述
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
举个例子：
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
思路解析
题目要求不能使用除法，时间复杂度为O(n)，其中n为nums的长度。
首先引入两个概念，前缀积和后缀积。
前缀积：数组中第i个元素的前缀积为第i个元素之前所有元素的乘积。后缀积：数组中第i个元素的后缀积为第i个元素之后所有元素的乘积。
我们利用两个跟nums数组长度相同的数组，prefix用来存储nums的前缀积，postfix用来存储nums的后缀积。
prefix[0] = 1
prefix[i] = nums[0] * ... * nums[i-1], 0 < i < n
postfix[n-1] = 1
postfix[i] = nums[i+1] *... * nums[n-1], 0 <= i < n-1
数组res用来存储结果。
res[i] = prefix[i] * postfix[i], 0 <= i < n
对于数组nums = [1,2,3,4]，其计算流程如下：
最终结果为res=[24,12,8,6]。
C++代码
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int nums_len = nums.size();
vector<int> prefix(nums_len, 1);
vector<int> postfix(nums_len, 1);
vector<int> res(nums_len, 1);
//预生成前缀积数组
prefix[0] = 1;
for (int i = 1; i < nums_len; ++i) {
prefix[i] = prefix[i-1] * nums[i-1];
}
//预生成后缀积数组
postfix[nums_len - 1] = 1;
for (int j = nums_len - 2; j >= 0; --j) {
postfix[j] = postfix[j+1] * nums[j+1];
}
//生成结果
for (int k = 0; k < nums_len; ++k) {
res[k] = prefix[k] * postfix[k];
}
return res;
}
};
python代码
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
nums_len = len(nums)
prefix = [1] * nums_len
postfix = [1] * nums_len
res = [1] * nums_len
# 预生成前缀积数组
prefix[0] = 1
for i in range(1, nums_len):
prefix[i] = prefix[i-1] * nums[i-1]
# 预生成后缀积数组
postfix[nums_len - 1] = 1
for j in range(nums_len - 2, -1, -1):
postfix[j] = postfix[j+1] * nums[j+1]
# 生成结果
for k in range(nums_len):
res[k] = prefix[k] * postfix[k]
return res
代码优化
上面代码我们使用了三个数组prefix、postfix、res，造成了很大浪费。其实只需要一个res就够了，可以使用一个int型的变量代替数组，中间结果先存在res里面。
prefix[i] = prefix[i-1] * nums[i-1] => prefix = prefix * nums[i-1]
postfix[j] = postfix[j+1] * nums[j+1] => postfix = postfix * nums[j+1]
优化后的C++代码
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int nums_len = nums.size();
vector<int> res(nums_len, 1);
int prefix = 1;
for (int i = 0; i < nums_len; ++i) {
//正向遍历保存prefix结果到res
res[i] = prefix;
prefix = prefix * nums[i];
}
int postfix = 1;
for (int j = nums_len - 1; j >= 0; --j) {
//逆向遍历 中间结果（前缀积）乘以后缀积
res[j] = res[j] * postfix;
postfix = postfix * nums[j];
}
return res;
}
};
优化后的python代码
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
nums_len = len(nums)
res = [1] * nums_len
prefix = 1
for i in range(nums_len):
# 正向遍历保存prefix结果到res
res[i] = prefix
prefix *= nums[i]
postfix = 1
for j in range(nums_len - 1, -1, -1):
# 逆向遍历 中间结果（前缀积）乘以后缀积
res[j] *= postfix
postfix *= nums[j]
return res
复杂度分析
时间复杂度： 只需要遍历一遍nums，故时间复杂度是O(n)，其中n为nums的长度。
空间复杂度： 使用了一个res数组，故空间复杂度是O(n)，其中n为nums的长度。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
