从零学算法238

我们最容易想到的就是先求出所有数的乘积，然后用乘积除以每个数即可，但是题目要求不用除法。那我们肯定是用乘法，我们在求某个元素对应的结果时，只要有左边数组的乘积和右边数组的乘积，两数相乘就是答案，所以我们用两个数组记录，left[i] 表示下标为 i 元素左边数组的乘积，right[i] 表示下标为 i 元素右边数组的乘积。

  public int[] productExceptSelf(int[] nums) {
      int n = nums.length;
      int[] left = new int[n];
      // 首位元素左边没数字，所以乘积默认为 1
      left[0] = 1;
      int[] right = new int[n];
      // 同理末尾元素右边没数字，所以乘积默认为 1
      right[n-1] = 1;
      // 获取每个元素左边所有元素的乘积
      for(int i=1;i<n;i++){
          left[i]=left[i-1]*nums[i-1];
      }
      // 获取每个元素右边所有元素的乘积
      for(int i=n-2;i>=0;i--){
          right[i] = right[i+1]*nums[i+1];
      }
      int[] res = new int[n];
      // 每个元素对应结果等于左右乘积相乘
      for(int i=0;i<n;i++){
          res[i]=left[i]*right[i];
      }
      return res;
  }

那其实我们在获取每个元素右边的乘积的时候，每获得一个其实就能得到一个元素对应的结果了，所以可以合并第 2,3 个 for 循环

  public int[] productExceptSelf(int[] nums) {
      int n = nums.length;
      int[] left = new int[n];
      // 首位元素左边没数字，所以乘积默认为 1
      left[0] = 1;
      int[] right = new int[n];
      // 同理末尾元素右边没数字，所以乘积默认为 1
      right[n-1] = 1;
      // 获取每个元素左边所有元素的乘积
      for(int i=1;i<n;i++){
          left[i]=left[i-1]*nums[i-1];
      }
      // 获取每个元素右边所有元素的乘积
      // 同时获得该元素对应的结果
      int[] res = new int[n];
      // 该元素最右边的结果其实就是左边所有数的乘积
      res[n-1] = left[n-1];
      for(int i=n-2;i>=0;i--){
          right[i] = right[i+1]*nums[i+1];
          res[i]=left[i]*right[i];
      }
      return res;
  }

上面在获取右乘积时我们会发现，其实我们的每个 right[i] 只和他的前一个乘积有关，那我们都不需要数组，用一个变量不断更新即可

  public int[] productExceptSelf(int[] nums) {
      int n = nums.length;
      int[] left = new int[n];
      left[0] = 1;
      for(int i=1;i<n;i++){
          left[i]=left[i-1]*nums[i-1];
      }
      int[] res = new int[n];
      int right = 1;
      for(int i=n-1;i>=0;i--){
          res[i] = left[i]*right;
          right*=nums[i];
      }
      return res;
  }

题目最后说能否用 O(1) 的额外空间，结果数组 res 不算，那你直接把 res 当做 left 用即可

  public int[] productExceptSelf(int[] nums) {
      int n = nums.length;
      int[] res = new int[n];
      res[0] = 1;
      for(int i=1;i<n;i++){
          re[i]=res[i-1]*nums[i-1];
      }
      int right = 1;
      for(int i=n-1;i>=0;i--){
          res[i] *= right;
          right*=nums[i];
      }
      return res;
  }