lc238除自身以外数组的乘积——动态规划前缀积

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

不准使用除法...

法1：常规动态规划

想到类似前缀和，可以借用动态规划思想计算前缀积和后缀积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        int[] preDp = new int[n];
        preDp[0] = 1;
        int[] postDP = new int[n];
        postDP[n-1] = 1;

        for(int i=1;i<n;i++) {
            preDp[i] = preDp[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--) {
            postDP[i] = postDP[i+1]*nums[i+1];
        }

        int[] ans = new int[n];
        for(int i=0;i<n;i++) {
            ans[i] = preDp[i]*postDP[i];
        }
        return ans;
    }
}

不过这样空间复杂度为O(n)，能不能优化为O(1)呢？

法2:

如果只是单纯求某元素前缀积或者后缀积，我们可以优化空间复杂度为O(1)，但同时求2个的积理论上是不行的。但可以将ans[]要返回的答案数组同时也先作为前缀积数组（不算额外空间），然后求后缀积就用O(1)一个变量记录那种求法就能实现，额外空间复杂度为O(1)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        //直接ans也当做dpLeft[]数组用
        int[] ans = new int[n];
        //前缀积
        ans[0] = 1;
        for(int i=1;i<n;i++) {
            ans[i] = ans[i-1]*nums[i-1];
        }
        //后缀积
        // 可以直接用一个变量表示了，每次遍历只用到后面一个
        int right = nums[n-1];
        for(int i=n-2;i>=0;i--) {
            ans[i] *= right;
            right *= nums[i];
        }
        return ans;
    }
}

法3：双指针版动态规划

还有大佬想出双指针，一次遍历的做法，很巧妙

它是先将ans[]都初始化为1，然后每个ans[]元素都会被*2次，一次是*前缀积，一次是*后缀积。通过一次for循环遍历。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        int[] ans = new int[n];
        Arrays.fill(ans, 1);//初始化为1
        int left = 0;
        int right = n-1;
        int leftDpValue = 1;
        int rightDpValue = 1;

        for(int i=0; i<n; i++) {
            ans[left] *= leftDpValue;
            ans[right] *= rightDpValue;

            leftDpValue *= nums[left++];
            rightDpValue *= nums[right--];
        }
        return ans;
    }
}