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

238. 除了自身以外数组的乘积 - 力扣（LeetCode）

class Solution {
public:
  vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> Product(nums.size(), 1);
    vector<int> Left(nums.size(), 1);
    vector<int> Right(nums.size(), 1);

    for (int i = 1; i < nums.size(); ++i)
      Left[i] = Left[i - 1] * nums[i - 1];
    for (int i = nums.size() - 2; i >= 0; --i)
      Right[i] = Right[i + 1] * nums[i + 1];
    for (int i = 0; i < nums.size(); ++i)
      Product[i] = Left[i] * Right[i];

    return Product;
  }
};

这题 $\mathrm O(2n)$ 的 Left 和 Right 是用来记录前缀积和后缀积的，最后是用一个交叉相乘，比较直观；但是下面有一个双指针的做法特别优雅：

std::vector<int> productExceptSelf2(std::vector<int>& nums) {
    std::vector<int> answer(nums.size(), 1);
    int left = 0, right = nums.size() - 1;
    int lp = 1, rp = 1;
    while (right >= 0 && left < nums.size()) {
        answer[right] *= rp;
        answer[left] *= lp;
        lp *= nums[left++];
        rp *= nums[right--];
    }
    return answer;
}

右指针逐步得到右边积，左指针逐步得到左边积。当左右指针开始相遇时，答案开始变为正确，因为左右两侧的全积业已得到。可以发现，本题事实上并不需要记录完整的左右边积数组，只需要记录部分积即可——因为我们可以把部分积提前写入 answer 数组以供后面遇到对侧指针时使用。

二刷

class Solution {
public:
  vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> Left(nums.size(), 1);
    for (int i = 1; i < nums.size(); ++i)
      Left[i] = nums[i - 1] * Left[i - 1];
    // Multiplication identity.
    int Suffix = 1;
    for (int i = Left.size() - 1; i >= 0; --i) {
      int Val = nums[i];
      nums[i] = Suffix * Left[i];
      Suffix *= Val;
    }
    return nums;
  }
};

这是一种只用一组辅助空间 Left 的中间解法，利用了 nums 可修改的机制，原地计算本应开辟的 Right 空间——但是你再仔细想想，这个是不是还能继续往下优化呢？

答案就是，既然 Suffix 的计算永远提前于结果的写入，我们就可以动态地计算它，并且可以直接把计算的结果写入 Left。

$$ \begin{matrix} &[&1&1&2&6]&\to&&\text{Result}=\text{Left}\\ \gets&&24&12&4&1&&&\text{Prefix}\\ &[&1&2&3&4]&&&\text{nums} \end{matrix} $$

这样的方法甚至不需要你采用 Val 临时变量来保存可能会被 clobber 掉的 nums 里面的数——它们自始至终都是原本的样子。你甚至完全没有修改 nums 本身。

class Solution {
public:
  vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> Result(nums.size(), 1);
    // This will make Result temporarily equal to left prefix.
    for (int i = 1; i < nums.size(); ++i)
      Result[i] = nums[i - 1] * Result[i - 1];
    // Multiplication identity.
    int Suffix = 1;
    for (int i = Result.size() - 1; i >= 0; --i) {
      Result[i] *= Suffix;
      Suffix *= nums[i];
    }
    return Result;
  }
};

说实话这个题在不考虑输出数组占用空间的前提下，产生的这种优化思路还是得好好研究研究。有东西的，不是那么无脑的。

二刷

class Solution {
public:
  vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> Result(nums);
    // PRODUCE (write) left product.
    // vector<int> Left = RunOver(Result);
    int Left = 1;
    for (int i = 0; i < nums.size(); ++i) {
      Result[i] = Left;
      Left *= nums[i];
    }

    // RUN OVER (read) whole product.
    int Right = 1;
    for (int i = nums.size() - 1; i >= 0; --i) {
      Result[i] *= Right;
      Right *= nums[i];
    }
    return Result;
  }
};

这题终于是整明白了。要搞清楚，我们第一趟修改 Result 的目的是使得它成为所谓的 Left[] 数组，所以我们需要一边实时计算 Left，一边把它写进数组里，也即

$$ \text{Result}_\text{Left}\gets\text{Left} $$

虽然我们修改了 Result，但是无所谓啊，它就是要被修改的。

而第二趟修改 Result 则是为了获得真正的、最终的值，此时 Right 被实时计算出来，于是我们进行

$$ \text{Result}\gets\text{Result}_\text{Left}\cdot\text{Right} $$

的操作，从而得到最终答案。

注意，这两种操作都是有共时性的需求的，所以理论上来说我们其实需要设置一些临时变量用来保存数组原值——但其实吧，不用，因为我们压根没改过 nums[]，它里头存的就是原值。

三刷

class Solution {
public:
  vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> Result(nums.size());
    int Prefix = 1;
    for (int i = 0; i < nums.size(); ++i) {
      // Assignment.
      Result[i] = Prefix;
      Prefix *= nums[i];
    }
    Prefix = 1;
    for (int i = nums.size() - 1; i >= 0; --i) {
      // Multiplication and assignment.
      Result[i] *= Prefix;
      Prefix *= nums[i];
    }
    return Result;
  }
};

一正一逆，一赋值一乘法，微妙的不对称性，很好玩。