238. Product of Array Except Self

傳入一個整數數列nums，返回一個數列answers，answers[i]的值是nums排除nums[i]後所有元素的乘積。

https://leetcode.com/problems/product-of-array-except-self/

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

題目規定不可以用除法，還有使用O(n)來解。

如果可以用除法那就很簡單了，全部乘一遍，再逐筆替換值 nums[i] = 乘積/nums[i]
雖然這麼說，不過還是踩到雷了，如果數列裡面包含零的話就會出錯XD。
所以如果要用暴力解法的話，還要多考慮 1個零跟多個零這兩種case。

回到題目，先把範例展開來觀察

1 2 3 4

  1 1 1
2   2 2
3 3   3
4 4 4  

紅字每一行的乘積，即為該欄位的解答。觀察到上面的三角，是nums逐步遞增相乘的乘積，下方的三角也是，是nums逐步遞減的乘積。

所以只要把上下兩塊三角組合好再進行相乘，就是我們的答案了。

	public static int[] productExceptSelf(int[] nums) {
		
		//新增一個同樣大小的陣列
		int[] res = new int[nums.length];
		//第一個初始值需指定為1，否則最後上下相乘到此時，值會變為0
		res[0] = 1;

		//將上方的三角形放入res
		for (int i = 0, ans = 1; i < nums.length - 1; i++) {
			res[i + 1] = ans * nums[i];
			ans = res[i + 1];
		}
		//將下方的三角形乘入res
		for (int i = nums.length - 1, ans = 1; i > 0; i--) {
			res[i - 1] = res[i - 1] * ans * nums[i];
			ans = ans * nums[i];
		}
		return res;
	}