目录
题目链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）
题目链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例
示例 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 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
解法一：左右数组（小型动态规划）
这个问题可以通过两次遍历数组来解决，而不需要使用额外的空间（除了用于结果的数组之外），但这段代码巧妙地使用了两个辅助数组 left 和 right 来分别存储每个元素左侧所有元素的乘积和右侧所有元素的乘积，从而避免了在单次遍历中同时计算左右两侧乘积的复杂性。
实现思路
- 初始化：
- 首先，创建一个与输入数组
nums长度相同的数组left，用于存储每个元素左侧所有元素的乘积（包括元素本身位置为1的情况，因为元素本身不参与计算）。 - 同时，创建一个与
nums长度相同的数组right，用于存储每个元素右侧所有元素的乘积（同样，元素本身位置为1）。
- 首先，创建一个与输入数组
- 计算左侧乘积：
- 遍历
nums数组，从左到右。 - 对于
left数组的每个位置i，其值等于nums[i-1]（如果i > 0）与left[i-1]的乘积。如果i = 0，则left[0] = 1，因为没有元素在nums[0]的左侧。
- 遍历
- 计算右侧乘积：
- 遍历
nums数组，但这次是从右到左。 - 对于
right数组的每个位置i，其值等于nums[i+1]（如果i < len-1）与right[i+1]的乘积。如果i = len-1，则right[len-1] = 1，因为没有元素在nums[len-1]的右侧。
- 遍历
- 计算最终结果：
- 再次遍历
nums数组，这次是为了计算每个元素的最终结果。 - 对于
nums数组的每个位置i，其最终值等于left[i]（左侧所有元素的乘积）与right[i]（右侧所有元素的乘积）的乘积。
- 再次遍历
- 返回结果：
- 将修改后的
nums数组返回，此时nums数组的每个元素都已经是除了它自身以外所有元素的乘积了。
- 将修改后的
Java写法：
class Solution {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
if(len == 0){
return nums;
}
// 定义出两个数组分别表示左边的乘积和右边数组的乘积
// 这个思路有点和动态规划相似
// 0 1 2 3
// 1, 2, 3,4
// left 1, 1, 2,6
// right 24,12,4,1
int[] left = new int[len];
int[] right = new int[len];
// 填入左边乘积数组的值
// 初始化
left[0] = 1;
for(int i = 1; i < len ; i++){
left[i] = nums[i - 1] * left[i - 1];
}
// 填入右边乘积数组的值
right[len - 1] = 1;
for(int i = len - 2; i >= 0 ; i--){
right[i] = nums[i + 1] * right[i + 1];
}
for(int i = 0; i < len; i++){
nums[i] = left[i] * right[i];
}
return nums;
}
}运行时间
C++写法：
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> left(len);
vector<int> right(len);
left[0] = 1;
for(int i = 1; i < len; i++){
left[i] = nums[i - 1] * left[i - 1];
}
right[len - 1] = 1;
for(int i = len - 2; i >= 0; i--){
right[i] = nums[i + 1] * right[i + 1];
}
for(int i = 0; i < len; i++){
nums[i] = left[i] * right[i];
}
return nums;
}
};运行时间
时间复杂度以及空间复杂度
 |  |
总结
累了哥几个，最近有点焦虑了，不总结了哎
