1.本题最同样想到的方法便是遍历一遍数组，将所有元素相乘，之后再遍历一遍数组，将最终相乘值除以当前元素即可得到答案。但题目要求不能使用除法，且这样做如果遇到0就会出错。
2.本题可以设置两个数组，来分别记录当前元素左边所有元素的乘积和右边所有元素的乘积，最终再将两个值相乘就是每个元素对应的答案，总共需要三次for循环遍历。完整代码如下：
1. /**
2. * Note: The returned array must be malloced, assume caller calls free().
3. */
4. // 除自身以外数组的乘积，使用左右前缀乘积数组求解
5. int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
6. // 设置返回数组长度
7. *returnSize = numsSize;
8. // 分配结果数组空间
9. int* res = (int*)malloc(sizeof(int) * numsSize);
10. // l数组：l[i]表示i左侧所有元素乘积；r数组：r[i]表示i右侧所有元素乘积
11. int l[numsSize], r[numsSize];
12. int tmp = 1;
13. // 最左侧元素左边无元素，乘积为1；最右侧元素右边无元素，乘积为1
14. l[0] = 1, r[numsSize – 1] = 1;
15. // 正向遍历，计算左侧前缀乘积
16. for (int i = 1; i < numsSize; i++){
17. tmp *= nums[i – 1];
18. l[i] = tmp;
19. }
20. tmp = 1;
21. // 反向遍历，计算右侧后缀乘积
22. for (int i = numsSize – 2; i >= 0; i–){
23. tmp *= nums[i + 1];
24. r[i] = tmp;
25. }
26. // 当前位置结果 = 左侧乘积 * 右侧乘积
27. for (int i = 0; i < numsSize; i++){
28. res[i] = l[i] * r[i];
29. }
30. return res;
31. }
该算法时间复杂度和空间复杂度均为O(n)。
3.本题的进阶要求需要空间复杂度为O(1)，力扣官方给出的答案有些复杂，将结果数组当成记录“左边元素乘积”的数组，再额外设置一个R来跟随记录“右边元素乘积”，需要两遍for循环。
4.本题最优的解法是使用双指针，在一遍for循环中同时进行“左右元素乘积计算”。左右指针同时从数组两端出发，这样就能保证每个元素都会被“左边元素乘积”和“右边元素乘积”分别乘一次，得到最终的结果。完整代码如下：
1. /**
2. * Note: The returned array must be malloced, assume caller calls free().
3. */
4. // 除自身以外数组的乘积，双指针法，直接在结果数组上保存乘积，不额外开辟左右数组
5. int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
6. // 设置返回数组长度
7. *returnSize = numsSize;
8. // 分配结果数组空间
9. int* res = (int*)malloc(sizeof(int) * numsSize);
10. // 结果数组初始全部置1
11. for (int i = 0; i < numsSize; i++){
12. res[i] = 1;
13. }
14. // l左指针，r右指针；l_mul保存左侧累积乘积，r_mul保存右侧累积乘积
15. int l = 0, r = numsSize – 1;
16. int l_mul = 1, r_mul = 1;
17. // 一轮循环同时从左右两端计算乘积
18. for (int i = 0; i < numsSize; i++){
19. // 当前左位置乘上左侧累积乘积
20. res[l] *= l_mul;
21. // 当前右位置乘上右侧累积乘积
22. res[r] *= r_mul;
23. // 更新左侧累积乘积，左指针右移
24. l_mul *= nums[l++];
25. // 更新右侧累积乘积，右指针左移
26. r_mul *= nums[r–];
27. }
28. return res;
29. }
该算法时间复杂度为O(n)，空间复杂度为O(1)，是本题最优解。
