七七老师的白日梦

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

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

是什么？

除自己以外数相乘

怎么做？

左右两边乘积再相乘

思考

七七原本是想运用数组直接双循环乘的，一是时间复杂度就不对了，二是不好确定左右数的个数，问灵宝要思路后突然就明白这道题到底该怎么做了，把数组分成左右两个部分，分别计算左右两部分的累乘再相乘

代码

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
//        answer[0] = 1这个可不可以删掉？答案是不可以，因为不初始化这个数组后面会用到answer[i-1]
//        与其他的乘积，默认值零为出错（为什么多说一嘴呢？因为七七忘了，因为有默认值的存在也不报错）
        answer[0] = 1;
//这里是计算什么呢？是计算左边的元素的乘积，这道题需要这样子考虑，不能用除法，时间复杂度为O（m）
//不能出现双循环，只能循环一次，那就把题目要求分成两个部分，左边乘积和右边乘积，然后相乘
        for (int i = 1; i < n; i++) {
//这里是计算左边的乘积，answer[0]左边没有数，所以answer[0] = 1，之后就是累乘
            answer[i] = answer[i - 1] * nums[i - 1];
        }
//为什么定义这个数？因为最后一个数的右边肯定是没有数的，所以定义一个数，来保存右边的乘积
        int suffixProduct = 1;
//        可以看到这里把answer[0]带进来了
        for (int i = n - 1; i >= 0; i--) {
//            同上啦！累乘右边不过多一个数来处理最右边的情况
            answer[i] = answer[i] * suffixProduct;
            suffixProduct *= nums[i];
        }

        return answer;
    }
}

当然这里也带来除法的做法（题目没要求但是七七想知道）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        int zeroCount = 0;
        int totalProduct = 1;

        // 第一次遍历：计算总乘积和 0 的个数
        for (int num : nums) {
            if (num == 0) {
                zeroCount++;
            } else {
                totalProduct *= num;
            }
        }

        // 第二次遍历：计算 answer 数组
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (zeroCount > 1) {
                    answer[i] = 0; // 多个 0，结果为 0
                } else {
                    answer[i] = totalProduct; // 仅有一个 0，当前元素为 0
                }
            } else {
                if (zeroCount > 0) {
                    answer[i] = 0; // 原数组中有 0，结果为 0
                } else {
                    answer[i] = totalProduct / nums[i]; // 无 0，直接除法
                }
            }
        }

        return answer;
    }
}

感觉更简单，但是容易溢出和0处理不当。