题目主要信息

给定一个长度为 n 的数组 nums ，返回一个数组 res，res[i]是nums数组中除了nums[i]本身以外其余所有元素的乘积，即：res[i]= nums*[1]×*nums*[2]×......×num**s[i−1]×num**s[i+1]......×num**s[n]

1.请不要使用除法，并且在 O(n) 时间复杂度内完成此题。

2.题目数据保证res数组的元素都在 32 位整数范围内

3.有O(1)空间复杂度的做法，返回的res数组不计入空间复杂度计算

方法一：暴力搜索

具体方法

使用两层for循环，在每一轮循环的时候当前位置的元素不参与相乘，本方法是回超时的，所以本题不适合。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] timesExceptSelf (int[] nums) {
        // write code here
        int [] res = new int[nums.length];
        // 暴力搜索
        int n = nums.length;
        for(int i=0;i<n;i++){
            int sum = 1;
            for(int j=0;j<n;j++){
                if(i == j)
                    continue;
                sum *= nums[j];
            }
            res[i] = sum;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}{n}^2\mathrm{）}O（n^2）$，两层for循环
• 空间复杂度：$O\mathrm{（}1\mathrm{）}O（1）$，直接返回结果

方法二：左右乘积列表

具体方法

可以使用一个数组$resres$依次从数组的左侧相乘，走到每个位置i的时候存储的时候该位置左侧的乘积的值$res[i]res[i]$，然后在从右向左遍历,遍历到i的时候，将右侧的成绩$r\ast res[i]r\; *\; res[i]$就得到当前位置i的除去自身的乘积了。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] timesExceptSelf (int[] nums) {
        // write code here
        int n = nums.length;
        int []res = new int[n];
        res[0] = 1;
        // 求每个位置的左侧乘积
        for(int i=1;i<n;i++){
            res[i] = res[i-1]* nums[i-1];
        }
        
        int r = 1;
        for(int i = n-1;i>=0;i--){
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            res[i] = res[i] * r;
          // 更新r
            r *= nums[i];
        }
        
        return res;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，其中 $nn$指的是数组 $numsnums$的大小。分析与方法一相同。
• 空间复杂度：$O(1)O(1)$，输出数组不算进空间复杂度中，因此我们只需要常数的空间存放变量。