238. Product of Array Except Self
难度: Medium
刷题内容
原题连接
- https://leetcode.com/problems/two-sum
内容描述
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
解题方案
思路 1 **- 时间复杂度: O(N)*- 空间复杂度: O(N)***
前缀积和后缀积, 懒得实现了
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
思路 1 **- 时间复杂度: O(N)*- 空间复杂度: O(1)***
还是一样的思想，只不过不记录下来，而是采用边循环边更新的方式
beats 100.00%
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
res[i] = 1;
}
int left = 1;
for (int i = 0; i < nums.length - 1; i++) {
left *= nums[i];
res[i+1] *= left;
}
int right = 1;
for (int i = nums.length - 1; i > 0; i--) {
right *= nums[i];
res[i-1] *= right;
}
return res;
}
}
