238 除自身以外数组的乘积

题目

给定长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

进阶

你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)


实现

思路:乘积 = 当前数左边的乘积 * 当前数右边的乘积

                [1, 2, 3, 4]
   左边的乘积    [1, 1, 2, 6]
   右边的乘积    [24,12,4, 1]
结果 = 左*右     [24,12,8, 6] 
  • 状态:通过
  • 17 / 17 个通过测试用例
  • 执行用时: 304 ms, 在所有 C# 提交中击败了 100.00% 的用户
  • 内存消耗: 34.6 MB, 在所有 C# 提交中击败了 100.00% 的用户
public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        int len = nums.Length;
        int[] output1 = new int[len];//正向乘积
        int[] output2 = new int[len];//反向乘积
        output1[0] = 1;
        output2[len - 1] = 1;
        for (int i = 1; i < len; i++)
        {
            output1[i] = output1[i - 1]*nums[i - 1];
            output2[len - i - 1] = output2[len - i]*nums[len - i];
        }
        for (int i = 0; i < len; i++)
        {
            output1[i] *= output2[i];
        }
        return output1;
    }
}