本节博客是用前缀和算法求解“除自身以外数组的乘积”，有需要借鉴即可。

目录

• 1.题目
• 2.前缀和算法
• 3.变量求解
• 4.总结

  1.题目

  题目链接：LINK

  2.前缀和算法

  • 1.创建两个数组
    • 第一个数组第i位置表示原数组[0,i-1]之积
    • 第二个数组第i位置表示原数组[i+1,n-1]之积
    • 2.进行求解结果

      图解如下：

      参考代码如下：

      class Solution {
      public:
          vector productExceptSelf(vector& nums) 
          {
              //预处理前缀和数组
              int n = nums.size();
              vector f(n);
              vector g(n);
              f[0] = 1;
              g[n-1] = 1;
              for(size_t i = 1; i < n; i++)
              {
                  f[i] = f[i-1] * nums[i-1];
              }
              for(int i = n - 2; i >= 0; i--)
              {
                  g[i] =g[i+1] * nums[i+1];
              }
              //求结果
              vector ret(n);
              for(size_t i = 0; i < n; i++)
              {
                  ret[i] = f[i] * g[i];
              }
              return ret;
          }
      };
      

      3.变量求解

      下面我们来挑战一下这道题的进阶版本：要求我们空间复杂度O(1)

      显然，前缀和算法时间复杂度是O(N)，不满足题目要求，因而我们应该用变量求解。

      class Solution {
      public:
          vector productExceptSelf(vector& nums) 
          {
              //要求空间复杂度：O(1)
              int n = nums.size();
              int f = 1;//充当前缀积变量
              int g = 1;//充当后缀积变量
              vector ret(n,1);
              for(int i = 0; i
                  ret[i]*= f;
                  f *= nums[i];
              }
              for(int i = n - 1; i >= 0 ;i--)
              {
                  ret[i]*= g;
                  g*=nums[i];
              }
              return ret;
          }
      };
      

      当然，两次循环也可以合并一下，就成下面这个代码了：

      class Solution {
      public:
          vector productExceptSelf(vector& nums) 
          {
              //要求空间复杂度：O(1)
              int n = nums.size();
              int f = 1;//充当前缀积变量
              int g = 1;//充当后缀积变量
              vector ret(n,1);
              for(int i = 0; i
                  ret[i]*= f;
                  ret[n-1-i]*= g;
                  
                  f *= nums[i];
                  g *= nums[n-1-i];
              }
             
              return ret;
          }
      };
      

      注：两个代码在效率上并没有提升。后者比前者虽然看着少了一次循环，但是我感觉效率是一样的，该怎么算还是怎么算，只不过是两种不同的写法而已！

      4.总结

      这个题目是一个简单运用前缀和的简单题目。

      进阶方面来看：这个题用前缀和多开空间虽然可以，不过有点多余，因为我们记住那么多数没用，下一次要用的数是确定的，所以不用记那么多，记住下一次要用的数字就行。

      ---

      EOF