[数据结构与算法]一. 数组_前缀和数组_238. 除自身以外数组的乘积

题目描述
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
输出: [24,12,8,6]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/product-of-array-except-self

暴力方法：
1.要求nums的各个数相乘，除了当前的序号，并将结果放进当前序号中
2.首先第一层for循环，确定当前的序号，第二个for循环遍历所有数字
3.如果等于当前序号，就不相乘，其他情况都乘上对应的数字
4.没有通过测试用例，时间超时。

vector<int> productExceptSelf(vector<int>& nums) {
    int m = nums.size();
    vector<int> ret(m);

    for(int i = 0; i < m; i++) {
        int sum = 1;

        for(int j = 0; j < m; j++) {
            if(i != j) {
                sum *= nums[j];
            }
        }

        //存储结果
        ret[i] = sum;
    }

    return ret;
}

题目说：整个数组的乘积都在整数可表达的范围内
下面的方案不可行。

vector<int> productExceptSelf(vector<int>& nums) {
    int m = nums.size();
    vector<int> ret(m);
    int sum = 1;

    //这里先将所有数字乘起来
    for(int i = 0; i < m; i++) {
        sum *= nums[i];
    }

    //之后，在计算当前下标的时候，乘其他所有的数字，就相当于除去当前的值
    //但是，这里有个前提条件，如果有0的话，就需要单独处理，如果能判断出所有的情况的话，也是可以的，但是比较麻烦
    for(int i = 0; i < m; i++) {
        ret[i] = sum / nums[i];
    }

    return ret;
}

这个是我看到官网的提示的时候，想出来的，那里面提到了前缀和还有后缀和
1.首先我在这个位置创建m+1的前缀和还有m+1的后缀和数组
2.这里prefix[0] = suffix[m] = 1
3.计算前缀和，还有后缀和
4.计算每个位置的和，那么每个位置的话，就是前一个的前缀和乘以后一个的后缀和为当前序号的结果
空间复杂度是O(2m+2)，即O(m)
时间复杂度是O(m)

vector<int> productExceptSelf(vector<int>& nums) {
    int m = nums.size();
    //这里创建前缀和还有后缀和分别都是m+1大小的
    vector<int> prefix(m + 1), suffix(m + 1);
    //因为a[0]的前缀和是空的，所以前缀和需要一个单独的位置，其值为1
    //后缀和a[m-1]的后缀和是空的，所以需要单独的一个后缀和，其值为1
    //这里前缀的顺序比普通序号加1，后缀的顺序和普通的序号相同
    prefix[0] = suffix[m] = 1;

    //前缀和是从1开始，前面前缀和乘以当前元素
    for(int i = 1; i <= m; i++) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }

    //后缀和是从最后一个位置开始，后一个位置的后缀和乘以当前元素
    for(int i = m - 1; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i];
    }

    //当前位置等于前一个的前缀和乘以后一个的后缀和
    for(int i = 0; i < m; i++) {
        nums[i] = prefix[i] * suffix[i + 1];
    }

    return nums;
}

上面记录的前缀和还有后缀和都多了占用了一个位置，其实不用n+1位置，n个位置就够了

vector<int> productExceptSelf(vector<int>& nums) {
    int m = nums.size();
    vector<int> prefix(m), suffix(m);
    //这里prefix的位置0是对应于nums[0]的前缀
    prefix[0] = suffix[m - 1] = 1;

    //前缀和是从1开始，前面前缀和乘以当前元素
    //这里重新定义了，其中nums的下标和prefix下标都是一一对应的
    //nums[0]的前缀和是prefix[0]
    //nums[1]的前缀和就是prefix[0] * nums[0]
    //前缀和就是不包含该元素的前缀和
    for(int i = 1; i < m; i++) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }

    //后缀和是从最后一个位置开始，后一个位置的后缀和乘以当前元素
    for(int i = m - 2; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }

    //当前位置等于前一个的前缀和乘以后一个的后缀和
    //前缀和还有后缀和，还有nums下标一一对应的，所以这里直接取对应下标即可
    for(int i = 0; i < m; i++) {
        nums[i] = prefix[i] * suffix[i];
    }

    return nums;
}

时间复杂度是O(m)
空间复杂度不算输出向量是O(1)

vector<int> productExceptSelf(vector<int>& nums) {
    int m = nums.size();
    vector<int> ret(m);
    //首先写入前缀和
    //前缀和还有nums下标一一对应
    ret[0] = 1;

    for(int i = 1; i < m; i++) {
        ret[i] = ret[i - 1] * nums[i - 1];
    }

    //写入后缀和
    //首先保存最后一个元素，并给其赋值为1
    int temp = nums[m - 1];
    nums[m - 1] = 1;

    //写入前面的后缀和
    for(int i = m - 2; i >= 0; i--) {
        //首先要将当前元素保存下来，因为下次计算的时候需要使用
        //当前前缀和等于上一次的前缀和乘以上一个元素，上一个元素使用temp保存下来。
        int temp_swap = nums[i];
        nums[i] = nums[i + 1] * temp;
        temp = temp_swap;
    }

    //前缀和乘以后缀和得出结果，赋值到ret向量中
    for(int i = 0; i < m; i++) {
        ret[i] = ret[i] * nums[i];
    }

    return ret;
}

这里首先创建前缀和数组，而动态的创建后缀和数组。
直接将前缀和乘以后缀和，得到的结果放到对应的ret矩阵中

vector<int> productExceptSelf(vector<int>& nums) {
    int m = nums.size();
    vector<int> ret(m);
    ret[0] = 1;

    //继续填充ret后面的值，作为前缀和矩阵
    for(int i = 1; i < m; i++) {
        ret[i] = nums[i - 1] * ret[i - 1];
    }

    //这里动态生成后缀和，并且利用后缀和计算出结果
    int R = 1;

    //将结果写入到ret中，这里下标处等于前缀和乘以后缀和
    //前缀和保存在ret中，最后一个位置的后缀和是1，所以前缀和乘以后缀和即可
    //现在明白了，其实你要弄明白前缀和乘以后缀和即可，你要找到当前的前缀和还有后缀和
    for(int i = m - 1; i >= 0; i--) {
        ret[i] = ret[i] * R;
        R *= nums[i];
    }

    return ret;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    productExceptSelf(nums);
}

写到这里，我在https://leetcode-cn.com/circle/article/48kq9d/这篇文章中的数组部分算是做完了，这其中有悲伤有快乐，更多的是收获，感觉这部分的技巧性占大部分，当然也有的解题方法，但是我一直感觉刷题就应该刷动态规划、分支限界法这种的，但是，我也不知道下一步应该做什么，如果感觉我的方向不对的，可以在评论告诉我。或者你有好的方法，提升算法能力的。