題目
給定長度為 n 的整數(shù)數(shù)組 nums策泣，其中 n > 1，返回輸出數(shù)組 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積缚去。
示例:
輸入: [1,2,3,4]
輸出: [24,12,8,6]
說明: 請不要使用除法路克，且在 O(n) 時間復(fù)雜度內(nèi)完成此題樟结。
傳送門 leetcode 238
思路
- 類似動態(tài)規(guī)劃思想，分成左右兩部分精算，比如2的左邊是1瓢宦，右邊是3，4
- 把左邊乘積放入結(jié)果集中
- 從右邊遍歷灰羽，將右乘積放入結(jié)果集中即可
class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) return nums;
int[] res = new int[nums.length];
res[0] = 1;
for (int i = 1; i < nums.length; i++) {
res[i] = res[i - 1] * nums[i - 1];
}//得到左乘結(jié)果
int right = 1;
for (int i = nums.length - 1; i >= 0; i--) {
res[i] *= right;//乘以右邊得到最終結(jié)果
right *= nums[i];//得到右乘積結(jié)果
}
return res;
}
}
