发表于: 更新于: 浏览: 595

题目地址

题目描述

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

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

进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

解法

JAVA

class Solution {
    public int[] productExceptSelf(int[] nums) {
      int len = nums.length;
        int[] left = new int[len];
        int k = 1;
        for (int i = 0; i < len; i++) {
            left[i]= k;
            k*=nums[i];
        }
        k = 1;
        for (int i = len - 1; i >= 0; i--) {
            left[i]*=k;
            k*=nums[i];
        }
        return left;
    }
}

解题思路

  • 左右指针
    刚开始的想法，使用左右指针解法，从左边遍历乘积left到K,然后从数组的右边的遍历积right到K,然后左右的乘积left*right作为K的,即[k]=left*right
  • 利用数组
    假设我要求K+1的值，只需要将之前的left*K* (right(K+2))，(right(K+1))是K+1下标右边的乘积，先暂时不计算这个值，我们先考虑K+1的左边，这样就没必要每次从左往右，从那就从左往右遍历一遍是数组，k+1的下标记录从0到K的乘积就好了。
 int len = nums.length;
int[] left = new int[len];

由于K+1的位置记录到K的乘积，所以需要一个变量错开

 int k = 1;
 //由于下标为0的左边的乘积没有，我们记录为1
for (int i = 0; i < len; i++) {
//先赋值，比如0下标的就记录为1
left[i]= k;
//然后乘积当前的值，赋值给i+1
k*=nums[i];
}

此时left[]数组记录了从左到右每个下标的乘积，我们以[1,2,3,4]为例，从此时left[]的值为[1,1,2,6]
然后我们计算从右到左的乘积，
下标3时，1*6；
下标2时，4*2；
下标1时，34*1；
下标0时，34*2*1；
红色标记为left的下标的值，此时，i的位置的答案(i+1)*(i+2)...*(len)*left[i]
那么只要从右往左进行遍历，然后变量记录i位置右边的乘积，然后和left[i]`相乘

k = 1;
for (int i = len - 1; i >= 0; i--) {
left[i]*=k;
k*=nums[i];
}