除自身以外数组的乘积
这一题乍一看好像十分简单，先用一趟循环遍历所有数据，得到数据所有元素的乘积，再用一趟循环将这个乘积除以每个元素，这样不就得到了除自身以外数组的乘积吗？我们先来看看代码：
int* productExceptSelf(int* nums, int numsSize, int* returnSize){ int *ret = (int *)malloc(sizeof(int) * numsSize); *returnSize = numsSize; int sub = 1; for(int i = 0; i < numsSize; i++) sub *= nums[i]; for(int i = 0; i < numsSize; i++) ret[i] = sub / nums[i]; return ret; }
得到了这样的结果：
提示我们不能进行除0操作
我们来看看它给的错误用例：
这下我们就清楚了，当数组元素存在0时，由于不能进行除0操作，那我们这个最容易想到的方法就失效了，我们必须另寻出路。
方法一：构造左右乘积列表
假设我们要求下标为i的元素外数组的乘积，那我们可以分别求出它左边所有元素的乘积和右边所有元素的乘积，再相乘即可。而为了方便得到这两个乘积，我们可以构造两个数组，分别存储下标为i(0 <= i < numsSize)左边所有元素的乘积和右边所有元素的乘积
具体构造步骤如下：
- 定义两个数组
left，right其大小和给定数组的大小一致 left数组用来存放下标为i(0 <= i < numsSize)左边所有元素的乘积。当i为0（数组最左边的元素）时，其左边没有数据，因此left[0]为1。对于i > 0的情况，left[i] = left[i - 1] * nums[i - 1]（从左向右计算）- 同理对于
right数组，当i = numsSize - 1时（数组最右边的元素），其右边没有元素，因此right[numsSize - 1]为1。对于i < numsSize - 1的情况，right[i] = right[i + 1] * nums[i + 1]（从右向左计算）
构造动图：
得到了left和right两个数组，我们就可以通过索引i直接得到最后结果了
这个方法的时间复杂度和空间复杂度都为O(N)
int* productExceptSelf(int* nums, int numsSize, int* returnSize){ //为返回数组申请内存 int *ret = (int *)malloc(sizeof(int) * numsSize); *returnSize = numsSize; //申请左右乘积列表的内存 int *left = (int *)malloc(sizeof(int) * numsSize); int *right = (int *)malloc(sizeof(int) * numsSize); //得到左右乘积列表 left[0] = 1; right[numsSize - 1] = 1; for(int i = 1; i < numsSize; i++) left[i] = left[i - 1] * nums[i - 1]; for(int i = numsSize - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1]; //最后的结果就是数据左边所有元素的乘积乘以右边所有元素的乘积 for(int i = 0; i < numsSize; i++) ret[i] = left[i] * right[i]; //返回得到的结果 return ret; }
方法一的优化
尽管方法一已经可以较好地解决问题，但是由于方法一除了返回数组外，还额外申请了两个数组，因此空间复杂度为O(N)（返回的数组不计入空间复杂度），我们可以对方法一进行优化，从而使空间复杂度为O(1)
由于返回的数组和左右乘积列表left、right是相同的大小，因此我们可以直接在返回数组ret的基础上直接先求出left或者right，然后再通过一次循环来更新右边所有元素的乘积，就可以得到最后结果了。
以下我们以先在ret的基础上求出left为例：
int* productExceptSelf(int* nums, int numsSize, int* returnSize){ //为返回数组申请内存 int *ret = (int *)malloc(sizeof(int) * numsSize); *returnSize = numsSize; //在ret的基础上求出left（左边所有数的乘积） ret[0] = 1; for(int i = 1; i < numsSize; i++) ret[i] = ret[i - 1] * nums[i - 1]; //从右向左遍历数组，不断更新sub（右边所有元素的乘积），最后得到结果 int sub = 1; for(int i = numsSize - 1; i >= 0; i--) { ret[i] = ret[i] * sub; sub *= nums[i]; } return ret; }
这样，我们就不需要申请额外的空间，从而使空间复杂度为O(1)
（推荐）方法二：左右指针
我们可以维护两个指针leftSub、rightSub，这两个指针分别用来计算左边所有数的乘积和右边所有数的乘积
具体步骤如下：
- 和上面的方法类似，先用
leftSub，利用一趟循环从左向右遍历，得到每个位置左边所有数据的乘积（也可以先用right计算右边所有数据的乘积） - 然后再用
rightSub，用一趟循环从右向左遍历，利用ret[i] *= rightSub就可以得到最后的结果
int* productExceptSelf(int* nums, int numsSize, int* returnSize){ //为返回数组申请内存 int *ret = (int *)malloc(sizeof(int) * numsSize); *returnSize = numsSize; //求出左边所有数据的乘积 int leftSub = 1; for(int i = 0; i < numsSize; i++) { ret[i] = leftSub; leftSub *= nums[i]; } //在已经得到左边所有数据的乘积的基础上，在乘以右边所有数据的乘积，得到最后结果 int rightSub = 1; for(int i = numsSize - 1; i >= 0; i--) { ret[i] *= rightSub; rightSub *= nums[i]; } return ret; }
方法二优化
方法二我们用了两次循环来解决问题，实际上，我们可以将这两个循环合并到一起（整体逻辑一样）
int* productExceptSelf(int* nums, int numsSize, int* returnSize){ //为返回数组申请内存 int *ret = (int *)malloc(sizeof(int) * numsSize); *returnSize = numsSize; //将返回数组初始化为1 for(int i = 0; i < numsSize; i++) ret[i] = 1; /* leftSub从左边开始，不断更新左边所有数据的乘积 rightSub从右边开始，不断更新右边所有数据的乘积 */ int leftSub = 1; int rightSub = 1; for(int i = 0, j = numsSize - 1; i < numsSize; i++,j--) { ret[i] *= leftSub; ret[j] *= rightSub; leftSub *= nums[i]; rightSub *= nums[j]; } return ret; }
