题目描述：

  1. 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
  5. 示例:
  7. 输入: [1,2,3,4,5]
  8. 输出: [120,60,40,30,24]
  11. 提示：
  13. 所有元素乘积之和不会溢出 32 位整数
  14. a.length <= 100000

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

不能使用除法hhhh,那怎么说，用减法来实现一个除法运算吗？
还是说用什么其他方法？
看了一下官方题解，注意到了可以利用类似前缀和的思想，来维护某一个数两端的乘积。
双向维护一遍之后，再看具体某个数的位置即可知道结果（确实妙啊）

代码

  1. class Solution {
  2. public:
  3.     vector<int> constructArr(vector<int>& a) {
  4.         int len = a.size();
  5.         vector<int> left(len,1);
  6.         vector<int> right(len,1);
  7.         vector<int> ans(len,1);
  8.         //如果a的长度为0 或者1怎么说
  9.         if(len == 0) return ans;
  10.         if(len == 1) return left;
  11.         else{
  12.             int tmp =1;
  13.             for(int i = 0;i<len-1;i++){
  14.                 tmp *= a[i]; 
  15.                 left[i] = tmp;
  16.             }
  17.             tmp =1;
  18.             for(int j = len-1;j>0;j--){
  19.                 tmp *= a[j];
  20.                 right[j] = tmp;
  21.             }
  22.             for(int i=0;i<len;i++){
  23.                 if(i==0) ans[i] = right[1];
  24.                 else if(i==len-1) ans[i] = left[len-2];
  25.                 else ans[i] = left[i-1]*right[i+1];
  26.             }
  27.         }
  28.         return ans;
  30.     }

分析

时间复杂度 O(N)
空间复杂度 O(N)