LeetCode #238. 除自身以外的数组乘积

Source: Dev.to

使用除法的解法

时间复杂度： O(n) – 对数组进行两次线性遍历。
空间复杂度： O(1) 辅助空间（仅使用少量额外变量）。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        int zeroCount = 0;
        int product = 1;

        // First pass: compute product of non‑zero elements and count zeros
        for (int num : nums) {
            if (num == 0)
                zeroCount++;
            else
                product *= num;
        }

        // Second pass: fill the result array based on zero count
        for (int i = 0; i < n; i++) {
            if (zeroCount > 1) {
                result[i] = 0;
            } else if (zeroCount == 1) {
                result[i] = (nums[i] == 0) ? product : 0;
            } else {
                result[i] = product / nums[i];
            }
        }

        return result;
    }
}

双遍历解法（不使用除法）

此方法通过使用前缀积和后缀积来计算除当前元素外的所有元素的乘积。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];

        // Prefix product: result[i] holds product of all elements to the left of i
        result[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // Suffix product: multiply by product of elements to the right of i
        int suffix = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            result[i] *= suffix;
            suffix *= nums[i];
        }

        return result;
    }
}