LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 把当前数左边所有数的乘积和右边所有数的乘积保存到两个数组中，同时遍历两个数组，得到的乘积即为其他元素的乘积

class Solution {
 public:
  vector<int> productExceptSelf(vector<int>& nums) {
    int n = size(nums);
    vector<int> l(n, 1);
    vector<int> r(n, 1);
    for (int i = 1; i < n; ++i) {
      l[i] = l[i - 1] * nums[i - 1];
    }
    for (int i = n - 2; i >= 0; --i) {
      r[i] = r[i + 1] * nums[i + 1];
    }
    for (int i = 0; i < n; ++i) {
      l[i] *= r[i];
    }
    return l;
  }
};

• 可以只使用一个数组

class Solution {
 public:
  vector<int> productExceptSelf(vector<int>& nums) {
    int sz = size(nums);
    vector<int> res(sz, 1);
    for (int i = 1; i < sz; ++i) {
      res[i] = res[i - 1] * nums[i - 1];
    }
    int t = 1;
    for (int i = sz - 2; i >= 0; --i) {
      t = t * nums[i + 1];
      res[i] *= t;
    }
    return res;
  }
};