特定顺序遍历二维数组、二维数组的变换、前缀和数组——LeetCode

一、特定顺序遍历二维数组

1、螺旋矩阵（中等）

自己的想法

方法一：模拟

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.6 MB, 在所有 Java 提交中击败了57.79%的用户

class Solution {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        // 记录已经走的格数
        int count = 0;
        int rowMax = matrix.length;
        if (rowMax == 0) {
            return list;
        }
        int colMax = matrix[0].length;
        int rowMin = -1;
        int colMin = -1;
        // 计算应该走的格数
        int max = colMax * rowMax;
        int row = 0;
        int col = 0;
        while (count != max) {
            // 往右走
            while (col < colMax && count != max) {
                list.add(matrix[row][col++]);
                count++;
            }
            col--;
            rowMin++;
            // 往下走
            while (++row < rowMax && count != max) {
                list.add(matrix[row][col]);
                count++;
            }
            row--;
            colMax--;
            // 往左走
            while (--col > colMin && count != max) {
                list.add(matrix[row][col]);
                count++;
            }
            col++;
            rowMax--;
            // 往上走
            while (--row > rowMin && count != max) {
                list.add(matrix[row][col]);
                count++;
            }
            colMin++;
            row++;
            col++;
        }
        return list;
    }
}

2、螺旋矩阵 II（中等）

自己的想法

方法一：模拟

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.3 MB, 在所有 Java 提交中击败了92.49%的用户

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        // 记录当前走的单元数
        int count = 1;
        // 应该走的总单元数
        int sum = n * n;
        int[][] move =new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] is =new boolean[n][n];
        int row = 0,col = 0,index = 0;
        while(count <= sum){
            result[row][col] = count++;
            is[row][col] = true;
            int nextRow = row + move[index][0],nextCol = col + move[index][1];
            // 判断是否需要转弯
            if(nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n || is[nextRow][nextCol] ){
                index = ++index % 4;
            }
            row += move[index][0];
            col += move[index][1];
        }
        return result;
    }
}

3、对角线遍历（中等）

自己的想法

方法一：模拟

• 执行用时：2 ms, 在所有 Java 提交中击败了97.24%的用户
• 内存消耗：40.6 MB, 在所有 Java 提交中击败了63.18%的用户

class Solution {
    public static int[] findDiagonalOrder(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[0];
        }
        if (matrix.length == 1) {
            return matrix[0];
        }
        int rowMax = matrix.length;
        int colMax = matrix[0].length;
        int sum = rowMax * colMax, col = 0, row = 0, count = 0;
        int[] result = new int[sum];
        while (count != sum) {
            // 右上走
            while (row >= 0 && col < colMax && count != sum) {
                result[count++] = matrix[row--][col++];
            }
            // 越界回溯
            if (col == colMax) {
                col--;
                row += 2;
            } else if (row < 0) {
                row++;
            }
            // 左下走
            while (col >= 0 && row < rowMax && count != sum) {
                result[count++] = matrix[row++][col--];
            }
            // 越界回溯
            if (row == rowMax) {
                row--;
                col += 2;
            } else if (col < 0) {
                col++;
            }
        }
        return result;
    }
}

看题解后

方法二：对角线迭代和翻转

• 执行用时：8 ms, 在所有 Java 提交中击败了22.22%的用户
• 内存消耗：40.4 MB, 在所有 Java 提交中击败了75.79%的用户

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new int[0];
        }
        int rowMax = matrix.length;
        int colMax = matrix[0].length;
        int[] result = new int[rowMax * colMax];
        // 记录数组的下标
        int index = 0;
        ArrayList<Integer> list = new ArrayList<>();
        // rowMax + colMax - 1 为矩阵对角线的个数
        for (int i = 0; i < rowMax + colMax - 1; i++) {
            // 清空数组的元素
            list.clear();
            // 计算坐标
            int row = i < colMax ? 0 : i - colMax + 1;
            int col = i < colMax ? i : colMax - 1;
            // 将对角的值装入集合中
            while (row < rowMax && col > -1) {
                list.add(matrix[row][col]);
                ++row;
                --col;
            }
            // 如果对角线为偶数则进行翻转
            if (i % 2 == 0) {
                Collections.reverse(list);
            }
            // 将集合中的数加入到数组中
            for (Integer integer : list) {
                result[index++] = integer;
            }
        }
        return result;
    }
}

方法三：找规律

  通过观察不难发现，横坐标+纵坐标的和为偶数时都是往左上走的；和为奇数时都是往右下走的。所以可以根据横坐标+纵坐标的和来判断指针的走向。

• 执行用时：2 ms, 在所有 Java 提交中击败了97.24%的用户
• 内存消耗：40.5 MB, 在所有 Java 提交中击败了65.79%的用户

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return new int[]{};
        }
        if (matrix.length == 1) {
            return matrix[0];
        }
        int row = 0, col = 0;
        int rowMax = matrix.length;
        int colMax = matrix[0].length;
        int[] result = new int[rowMax * colMax];
        for (int i = 0; i < result.length; i++) {
            result[i] = matrix[row][col];
            // 偶数都是往右上
            if ((row + col) % 2 == 0) {
                if (col == colMax - 1) {
                    row++;
                } else if (row == 0) {
                    col++;
                } else {
                    row--;
                    col++;
                }
            } else {
                // 奇数都是往左下
                if (row == rowMax - 1) {
                    col++;
                } else if (col == 0) {
                    row++;
                } else {
                    row++;
                    col--;
                }
            }
        }
        return result;
    }
}

二、二维数组变换

1、重塑矩阵（简单）

自己的想法

方法一：直接赋值

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：39.6 MB, 在所有 Java 提交中击败了64.52%的用户

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        if (nums.length == 0 || nums.length * nums[0].length != r * c) {
            return nums;
        }
        int[][] result = new int[r][c];
        int row = 0, col = 0, n = nums[0].length;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (col == n) {
                    col = 0;
                    row++;
                }
                result[i][j] = nums[row][col++];
            }
        }
        return result;
    }
}

看题解后

方法二：除法和取模

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：39.4 MB, 在所有 Java 提交中击败了84.95%的用户

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        if (nums.length == 0 || nums.length * nums[0].length != r * c) {
            return nums;
        }
        int[][] result = new int[r][c];
        int count = 0, n = nums[0].length;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                result[i][j] = nums[count / n][count % n];
                count++;
            }
        }
        return result;
    }
}

2、旋转图像（中等）

自己的想法

方法一：每次循环中旋转 4 个单元格

  硬生生写了两个小时才写出来，恶心到我了（菜啊）。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.6 MB, 在所有 Java 提交中击败了73.83%的用户

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 用于方便计算旋转下标
        int nn = matrix.length - 1;
        // 记录什么时候换行
        int colMax = nn;
        int row = 0, col = 0;
        while (row <= (n / 2 - 1)) {
            // 向右转
            int tmp = matrix[col][nn - row];
            matrix[col][nn - row] = matrix[row][col];
            // 向下转
            matrix[row][col] = tmp;
            tmp = matrix[nn - row][nn - col];
            matrix[nn - row][nn - col] = matrix[row][col];
            // 向左转
            matrix[row][col] = tmp;
            tmp = matrix[nn - col][row];
            matrix[nn - col][row] = matrix[row][col];
            // 向上转
            matrix[row][col] = tmp;
            col++;
            // 换行
            if (col == colMax) {
                colMax--;
                row++;
                col = row;
            }
        }
    }
}

看题解后

  简化移动的代码。

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 用于方便计算旋转下标
        int nn = matrix.length - 1;
        // 记录时候换行
        int colMax = nn;
        int row = 0, col = 0;
        while (row <= (n / 2 - 1)) {
            int tmp = matrix[row][col];
            matrix[row][col] = matrix[nn - col][row];
            matrix[nn - col][row] = matrix[nn - row][nn - col];
            matrix[nn - row][nn - col] = matrix[col][nn - row];
            matrix[col][nn - row] = tmp;
            col++;
            // 换行
            if (col == colMax) {
                colMax--;
                row++;
                col = row;
            }
        }
    }
}

  另一种移动方法。

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < (n + 1) / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
                matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = matrix[i][j];
                matrix[i][j] = temp;
            }
        }
    }
}

方法二：转置加翻转

  先将每一行的数据反转，然后再将矩阵中的数据对角交换。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.4 MB, 在所有 Java 提交中击败了87.50%的用户

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
                matrix[n - 1 - j][n - 1 - i] = tmp;
            }
        }
    }
}

3、矩阵置零（中等）

自己的想法

方法一：使用额外空间，记录需要置为 0 的行和列。

• 执行用时：2 ms, 在所有 Java 提交中击败了43.64%的用户
• 内存消耗：39.8 MB, 在所有 Java 提交中击败了90.99%的用户

class Solution {
    public void setZeroes(int[][] matrix) {
        // 记录需要设置 0 的行
        Set<Integer> row = new HashSet<>();
        // 记录需要设置 0 的列
        Set<Integer> col = new HashSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row.add(i);
                    col.add(j);
                }
            }
        }
        for (int i : row) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[i][j] = 0;
            }
        }
        for (int i : col) {
            for (int j = 0; j < matrix.length; j++) {
                matrix[j][i] = 0;
            }
        }
    }
}

看题解后

方法二：O(1)，使用首行首列记录当前行列是否要设置为 0，下标 (0,0) 需要特殊处理。

• 执行用时：1 ms, 在所有 Java 提交中击败了99.89%的用户
• 内存消耗：40.1 MB, 在所有 Java 提交中击败了67.14%的用户

class Solution {
    public void setZeroes(int[][] matrix) {
        // 记录需不需将第一列设置为0，下标（0，0）记录第 0 行是否设置为 0，该变量记录 0 列是否设置为 0
        boolean is = false;
        for (int i = 0; i < matrix.length; i++) {
            // 如果 j = 0 则表示需要将 0 列设置为 0
            if (matrix[i][0] == 0) {
                is = true;
            }
            // 从第二列开始找
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 设置列为 0
        for (int i = 1; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                for (int j = 1; j < matrix.length; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
        // 设置行为 0
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < matrix[0].length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 判断第一列是否要设置为 0
        if (is) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

4、生命游戏（中等）

自己的想法

方法一：额外空间

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.6 MB, 在所有 Java 提交中击败了91.69%的用户

class Solution {
    public void gameOfLife(int[][] board) {
        // 创建一个新数组用来存储原数组的值
        int[][] array = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            System.arraycopy(board[i], 0, array[i], 0, board[0].length);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 获取当前单元格的8个值
                int count = 0;
                // 上
                if (i - 1 >= 0) {
                    count += array[i - 1][j];
                }
                // 左
                if (j - 1 >= 0) {
                    count += array[i][j - 1];
                }
                // 左上
                if (i - 1 >= 0 && j - 1 >= 0) {
                    count += array[i - 1][j - 1];
                }
                // 下
                if (i + 1 < board.length) {
                    count += array[i + 1][j];
                }
                // 右
                if (j + 1 < board[0].length) {
                    count += array[i][j + 1];
                }
                // 右下
                if (i + 1 < board.length && j + 1 < board[0].length) {
                    count += array[i + 1][j + 1];
                }
                // 左下
                if (j - 1 >= 0 && i + 1 < board.length) {
                    count += array[i + 1][j - 1];
                }
                // 右上
                if (j + 1 < board[0].length && i - 1 >= 0) {
                    count += array[i - 1][j + 1];
                }
                if (board[i][j] == 1) {
                    if (count < 2) {
                        board[i][j] = 0;
                    } else if (count > 3) {
                        board[i][j] = 0;
                    }
                } else {
                    if (count == 3) {
                        board[i][j] = 1;
                    }
                }
            }
        }
    }
}

看题解后

方法二：额外状态

  遍历矩阵，使用额外状态对修改后的状态进行标记，如：

• 用 -1 记录原来是活的，现在是死的；
• 用 2 记录原来是死的现在是活的。

  最后再遍历矩阵对额外状态进行复原即可。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.6 MB, 在所有 Java 提交中击败了86.43%的用户

class Solution {
    public void gameOfLife(int[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 获取当前单元格的8个值
                int count = 0;
                // 上
                if (i - 1 >= 0) {
                    count += getOriginal(board[i - 1][j]);
                }
                // 左
                if (j - 1 >= 0) {
                    count += getOriginal(board[i][j - 1]);
                }
                // 左上
                if (i - 1 >= 0 && j - 1 >= 0) {
                    count += getOriginal(board[i - 1][j - 1]);
                }
                // 下
                if (i + 1 < board.length) {
                    count += getOriginal(board[i + 1][j]);
                }
                // 右
                if (j + 1 < board[0].length) {
                    count += getOriginal(board[i][j + 1]);
                }
                // 右下
                if (i + 1 < board.length && j + 1 < board[0].length) {
                    count += getOriginal(board[i + 1][j + 1]);
                }
                // 左下
                if (j - 1 >= 0 && i + 1 < board.length) {
                    count += getOriginal(board[i + 1][j - 1]);
                }
                // 右上
                if (j + 1 < board[0].length && i - 1 >= 0) {
                    count += getOriginal(board[i - 1][j + 1]);
                }
                if (board[i][j] == 1) {
                    if (count < 2) {
                        board[i][j] = -1;
                    } else if (count > 3) {
                        board[i][j] = -1;
                    }
                } else {
                    if (count == 3) {
                        board[i][j] = 2;
                    }
                }
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = getNow(board[i][j]);
            }
        }
    }

    // 用来将特殊状态转为原状态
    public int getOriginal(int value) {
        if (value == -1) {
            return 1;
        } else if (value == 2) {
            return 0;
        } else {
            return value;
        }
    }

    // 用来将特殊状态转为现在状态
    public int getNow(int value) {
        if (value == -1) {
            return 0;
        } else if (value == 2) {
            return 1;
        } else {
            return value;
        }
    }
}

三、前缀和数组

1、区域和检索 - 数组不可变（简单）

自己的想法

方法一：暴力破解

• 执行用时：80 ms, 在所有 Java 提交中击败了20.79%的用户
• 内存消耗：41.3 MB, 在所有 Java 提交中击败了77.89%的用户

class NumArray {

    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
    }

    public int sumRange(int i, int j) {
        int sum = 0;
        for (int a = i; a <= j; a++) {
            sum += nums[a];
        }
        return sum;
    }
}

看题解后

方法二：缓存（超时）

  将数组中的所有区间的和，存入 Map 集合中（Key 为坐标，Value 为和）。

class NumArray {

    Map<Pair, Integer> map = new HashMap<>();

    public NumArray(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                map.put(new Pair(i, j), sum);
            }
        }
    }

    public int sumRange(int i, int j) {
        return map.get(new Pair(i, j));
    }

    private class Pair {
        int i;
        int j;

        public Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }

        @Override
        public boolean equals(Object o) {
            Pair pair = (Pair) o;
            return i == pair.i && j == pair.j;
        }

        @Override
        public int hashCode() {
            return Objects.hash(i, j);
        }
    }
}

方法三：预处理

  对数组进行预处理，数组 array[i+1] 存放 nums[0]~nums[i] 的和。nums[i]~nums[j] 的和为 array[j+1]-array[i]。

• 执行用时：9 ms, 在所有 Java 提交中击败了99.65%的用户
• 内存消耗：41.4 MB, 在所有 Java 提交中击败了68.51%的用户

class NumArray {

    int[] array;

    public NumArray(int[] nums) {
        array = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            array[i + 1] = array[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return array[j + 1] - array[i];
    }
}

2、二维区域和检索 - 矩阵不可变（中等）

自己的想法

方法一：按行预处理

  不理解的，可以先看看上一题的方法三。

• 执行用时：15 ms, 在所有 Java 提交中击败了76.78%的用户
• 内存消耗：44 MB, 在所有 Java 提交中击败了82.08%的用户

class NumMatrix {

    int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0) {
            return;
        }
        dp = new int[matrix.length][matrix[0].length + 1];
        // 对矩阵的每一行进行预处理
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dp[i][j + 1] = dp[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += dp[i][col2 + 1] - dp[i][col1];
        }
        return sum;
    }
}

方法二：对矩阵进行预处理

  如图：红色区域 = 整个矩阵 - 蓝色区域 - 黄色区域 + 绿色区域。

  我们可以对矩阵进行预处理，让单元格 [i, j] 的值等于矩阵 [0, 0]~[i, j] 的值，[i, j] = [i, j] + [i-1, j] + [i, j-1] - [i-1, j-1]。当我们需要红色区域的值时，就可以通过公式算出，从而提升效率。

• 执行用时：14 ms, 在所有 Java 提交中击败了98.39%的用户
• 内存消耗：44.2 MB, 在所有 Java 提交中击败了54.89%的用户

class NumMatrix {

    int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0) {
            return;
        }
        dp = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
}

3、除自身以外数组的乘积（中等）

方法一：除法

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：48.8 MB, 在所有 Java 提交中击败了49.43%的用户

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        // 记录数组所有元素的积
        int product = 1;
        // 记录数组中 0 的下标
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                // 如果数组中有两个 0，则数组中的元素积全为 0
                if (index != -1) {
                    return result;
                }
                // 记录 0 的下标
                index = i;
            } else {
                product *= nums[i];
            }
        }
        // 如果数组中没有 0，则直接用积除以当前元素
        if (index == -1) {
            for (int i = 0; i < nums.length; i++) {
                result[i] = product / nums[i];
            }
        } else {
            // 如果数组中有一个 0，则除了 0 下标的值为非 0，其他值都为 0
            result[index] = product;
        }
        return result;
    }
}

方法二：左右乘积列表

  创建两个数组 left 和 right。对于给定索引 i，left[i] 代表的是 i 左侧所有数字的乘积，right[i]代表的是 i 右侧所有数字的乘积。

• 执行用时：3 ms, 在所有 Java 提交中击败了8.71%的用户
• 内存消耗：51.5 MB, 在所有 Java 提交中击败了11.59%的用户

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        // 左乘积
        int[] left = new int[n];
        // 右乘积
        int[] right = new int[n];
        // 对于索引为 0 的元素，因为左（右）侧没有元素，所以为 1
        left[0] = 1;
        right[n - 1] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
            right[n - 1 - i] = right[n - i] * nums[n - i];
        }
        // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for (int i = 0; i < n; i++) {
            result[i] = left[i] * right[i];
        }
        return result;
    }
}

方法三：左右乘积，空间复杂度 O(1)

  题目说输出数组不被视为额外空间，所以我们可以用 result 数组，构建左乘积列表。倒序遍历 result 数组，然后通过乘以右乘积为数组重新赋值。因为是倒序遍历，所以可以用一个变量 right 记录右乘积，right 初值为 1，每次循环执行 right *= nums[i] 即可计算出右乘积。

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：49 MB, 在所有 Java 提交中击败了39.20%的用户

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        result[0] = 1;
        // 首先计算左侧的乘积
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        // 记录右边的乘积
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }
        return result;
    }
}