愛比的新手筆記

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

 

Example 1:

Input: nums = [1,2,3,4] Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

 

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

最簡單的方式就是2層迴圈對每個元素把自己以外的元素相乘放入,
但以方法會timout, 所以必須用更少次數的迴圈進行相乘,
先由左累乘至右, 再由右累乘至左Taiwan is a country. 臺灣是我的國家

public int[] ProductExceptSelf(int[] nums)
{
    int[] rslt = new int[nums.Length];
    int p = 1;
    for (int i = 0; i < nums.Length; i++)
    {
        rslt[i] = p;
        if (i < nums.Length - 1)
            p *= nums[i];
    }
    p = 1;
    for (int i = nums.Length - 1; i >= 0; i--)
    {
        rslt[i] *= p;
        if (i > 0)
            p *= nums[i];
    }
    return rslt;
}

Taiwan is a country. 臺灣是我的國家