leetcode每日一题——238.除自身以外数组的乘积（面试经典150题）_给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中

一、题目描述与要求

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 位 整数范围内

---

二、解题思路

总的思路：

       先分析题目可知，题目要求我们计算所给数组中除了每一个元素自身以外的所有元素的乘积，并将这个乘积依次存储到answer数组中。基于这个要求我们可以想到利用双重for循环即可求解，但是题目又要求我们要在O(n)时间复杂度内完成，基于这个要求我们可以想到利用for循环计算出整个数组的乘积然后依次除以对应元素，但题目又说了不能够使用除法。因此，我们需要在至多只能使用一层for循环并且不使用除法的基础上去求出最终结果。

      我们可以这么分析，除了每一个元素自身以外的数是不是分别分布在其左右两侧，我们求对应的answer时难点就在于跳过这个数自身。那我们是不是可以考虑以对应元素为分界线，然后分别求出其左边所有元素的乘积以及其右边所有元素的乘积，然后把这两个乘积相乘来得到最后的结果。因为我们只需要求左边或者右边的全部，那就不需要跳过，所以可以利用一层for循环直接得到结果。显然，记录对应的左边元素乘积还有右边元素乘积也是用数组来存储数据。

       其中第一个元素和最后一个元素是没有左边（右边）元素的，所以在求左边乘积的时候，i从1开始，求右边乘积的时候，i从numsSize-2开始。计算左边乘积的公式为left[i]=left[i-1]*nums[i-1]。其中left[i]的含义是指数组中下标为i的元素的左边元素的乘积，因而可以利用前一个数左边的乘积乘以前一个数就可以得到当前元素的左边乘积。右边也是一样，right[i]=right[i+1]*nums[i+1]。分别求出来之后，直接将两个结果分别相乘，把值赋值给answer数组即可。

具体步骤：

①定义用来存储结果的两个数组以及最终要返回的数组

②求每个元素其左边所有元素的乘积，并存储到left数组中

③求每个元素其右边所有元素的乘积，并存储到right数组中

④求左乘积与右乘积的乘积，并存储到answer数组中

⑤返回answer数组

---

三、具体代码【C语言】

/**
 * Note: The returned array must be malloced, assume caller calls free().
   意思是：返回的数组要利用malloc申请空间
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    //要求计算除自身以外数组的乘积，如果不限制时间复杂度则可以直接利用双重循环求结果
    //但题目要去时间复杂度为O(n)，因此我们最多只能够使用一层for循环
    //所要得到的乘积可以转变成分别求其左右两边的乘积后相乘的结果。
    int left[numsSize];//用来存储每个数的左边乘积
    int right[numsSize];//用来存储每个数的右边乘积
    *returnSize = numsSize;//返回数组的大小与原数组相等
    int * answer = (int *)malloc(sizeof(int) * numsSize);//为answer数组申请空间
 
    //左乘积
    left[0] = 1;//相乘而不是加减，所以初始化为1
    //第一个元素左边没有数据，因此从下标为1的元素开始计算
    for(int i = 1; i < numsSize; i++)
    {
        left[i] =  left[i-1] *  nums[i-1];//计算不包括自身在内的左边的数的乘积
    }
 
    //右乘积
    right[numsSize-1] = 1;
    //最后一个元素的右边没有数据，因此从下标为numsSize-2开始计算
    for(int i = numsSize-2; i  >= 0 ; i--)
    {
        right[i] =  right[i+1] *  nums[i+1];//计算不包括自身在内的右边的数的乘积
    }
    for(int i =0; i < numsSize; i++)
    {
        answer[i] = left[i] * right[i];//将每个数左右两边的乘积相乘得到最后结果
    }
    return answer;
}