力扣面试经典——238题

💡 参考代码：

/**
 * 计算数组中除当前元素外其余各元素的乘积
 * @param nums       输入的整数数组
 * @param numsSize   输入数组的大小
 * @param returnSize 输出数组的大小，由函数设置
 * @return           返回结果数组，其中每个元素是除对应位置外其余元素的乘积
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    // 分配结果数组空间
    int* answer = (int*)malloc(numsSize * sizeof(int));
    *returnSize = numsSize;
    
    // 第一次遍历：计算每个元素左侧所有元素的乘积
    // answer[i] 存储 nums[0] 到 nums[i-1] 的乘积
    answer[0] = 1;
    for (int i = 1; i < numsSize; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }
    
    // 第二次遍历：从右向左遍历，将右侧元素乘积与左侧乘积相乘
    // rightProduct 记录当前元素右侧所有元素的乘积
    int rightProduct = 1;
    for (int i = numsSize - 1; i >= 0; i--) {
        answer[i] = answer[i] * rightProduct;
        rightProduct *= nums[i];
    }
    
    return answer;
}

📖 总结：

点击展开题目总结

🤔 除自身以外数组的乘积

---

1️⃣ 题目核心信息

🎯 功能描述：计算数组中除当前元素外其余各元素的乘积，不使用除法并在O(n)时间复杂度内完成

📥 输入输出：

• 输入：nums整数数组，numsSize数组长度
• 输出：返回新数组，其中每个元素是除对应位置外其余元素的乘积

---

2️⃣ 实现原理

💡 核心思路：利用前缀乘积和后缀乘积的思想，将每个位置的结果分解为左侧元素乘积与右侧元素乘积的乘积

📋 实现步骤：

1. 第一次遍历从左到右，计算每个位置左侧所有元素的乘积并存储
2. 初始化右侧乘积变量为1
3. 第二次遍历从右到左，将每个位置的左侧乘积与右侧乘积相乘
4. 在遍历过程中动态更新右侧乘积值

---

3️⃣ 关键点解析

🎯 代码技巧

• 利用输出数组存储左侧乘积，节省额外空间
• 使用单变量跟踪右侧乘积，避免额外数组存储
• 两次单层循环实现O(n)时间复杂度

4️⃣ 使用场景

✅ 适用情况：

• 需要计算数组元素间乘积关系的场景
• 不能使用除法运算的情况
• 对空间复杂度有严格要求的场景

⚠️ 前提条件：

• 输入数组至少包含两个元素
• 数组中元素的前缀和后缀乘积在32位整数范围内

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n)，需要遍历数组两次

• 💾 空间复杂度：O(1)，不考虑输出数组的情况下只使用常数额外空间

6️⃣ 注意事项

🚩 边界情况：

• 数组中包含0元素的情况
• 数组长度为2的最小情况
• 正负数混合的情况

💥 易错点：

• 忘记设置returnSize参数
• 混淆左侧乘积和右侧乘积的计算方向
• 内存分配后忘记检查是否成功

7️⃣ 补充说明

算法原理解析

int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    // 分配结果数组空间
    int* answer = (int*)malloc(numsSize * sizeof(int));
    *returnSize = numsSize;
    
    // 第一次遍历：计算每个元素左侧所有元素的乘积
    // answer[i] 存储 nums[0] 到 nums[i-1] 的乘积
    answer[0] = 1;
    for (int i = 1; i < numsSize; i++) {
        answer[i] = answer[i - 1] * nums[i - 1];
    }
    
    // 第二次遍历：从右向左遍历，将右侧元素乘积与左侧乘积相乘
    // rightProduct 记录当前元素右侧所有元素的乘积
    int rightProduct = 1;
    for (int i = numsSize - 1; i >= 0; i--) {
        answer[i] = answer[i] * rightProduct;
        rightProduct *= nums[i];
    }
    
    return answer;
}

这个算法的巧妙之处在于分而治之的思想，让我用更直观的方式来解释：

核心思想

对于数组中任意位置 i，我们要求的结果是：

result[i] = (nums[0] × nums[1] × ... × nums[i-1]) × (nums[i+1] × ... × nums[n-1])

也就是：左侧所有元素的乘积 × 右侧所有元素的乘积

为什么这样做是正确的？

第一次遍历：计算左侧乘积

answer[i] = nums[0] × nums[1] × ... × nums[i-1]

对于 nums = [1, 2, 3, 4]：

• answer[0] = 1 (左侧无元素)
• answer[1] = 1 (左侧: nums[0] = 1)
• answer[2] = 1×2 = 2 (左侧: nums[0]×nums[1] = 1×2)
• answer[3] = 1×2×3 = 6 (左侧: nums[0]×nums[1]×nums[2] = 1×2×3)

第二次遍历：乘以右侧乘积

使用 rightProduct 变量从右往左累积右侧元素乘积：

• 当处理 answer[3] 时：右侧无元素，rightProduct = 1
  • answer[3] = 6 × 1 = 6
• 当处理 answer[2] 时：右侧只有 nums[3] = 4，rightProduct = 4
  • answer[2] = 2 × 4 = 8
• 当处理 answer[1] 时：右侧是 nums[2]×nums[3] = 3×4 = 12，rightProduct = 12
  • answer[1] = 1 × 12 = 12
• 当处理 answer[0] 时：右侧是 nums[1]×nums[2]×nums[3] = 2×3×4 = 24，rightProduct = 24
  • answer[0] = 1 × 24 = 24

关键洞察

这个算法的精妙在于：

1. 空间复用：用结果数组 answer 先存储左侧乘积，避免额外空间
2. 累积计算：rightProduct 在遍历过程中逐步累积右侧乘积
3. 时机把握：在更新 rightProduct 之前先完成当前元素的计算

数学验证

对于任意位置 i：

• 第一次遍历后：answer[i] = 左侧乘积
• 第二次遍历时：answer[i] = answer[i] × rightProduct = 左侧乘积 × 右侧乘积

这就是所求的结果！

加载评论中...