算法题（数组篇）

1、简介

分类刷算法题（语言：java）：

​ 博主将陆续按分类顺序发布力扣算法题的解析与代码。部分代码参考力扣解析，仅供参考，如有疑问，评论探讨。

数组篇：

遇到不会的排序试试

正向走不通反向思考

2、例题推荐

2.1、数组的遍历

485. 最大连续 1 的个数

题目：

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int len = nums..length;  //数组长度
        int cur_num = 0;  //当前1的数量
        int max = 0;  //最大连续1的数量
        for (int i = 0; i < len; i++) {  //循环遍历数组元素
            if (nums[i] == 0) {  //当前元素为0时，将当前记录1的数量设为0
                index = 0;
            }
            else {  //当前元素为1的情况
                index++; 
                if (index > max){  //每次都与最大值比较，当前1的数量大于max，就赋值给max
                    max = index;
                }
            }
        }
        return max;
    }
}

495.提莫攻击

题目：

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int poisoning_time = 0;  //中毒时间
        if (timeSeries..length == 1) {
            return duration;  //如果数组只有一个数据，相当于攻击一次，就直接返回持续时间即可
        }
        for (int i = 0; i < timeSeries..length; i++) {
            if (i == timeSeries..length-1) {
                poisoning_time += duration;  //最后一次攻击，直接把中毒时间加上持续时间
                break;
            }else{
                if (timeSeries[i+1] - timeSeries[i] >= duration){  //两次攻击时间大于持续时间
                	poisoning_time += duration;
            	}else{
                	poisoning_time += timeSeries[i+1] - timeSeries[i];  //两次攻击时间小于持续时间，直接加上时间差
            	}
            }
        }
        return poisoning_time;
    }
}

414.第三大的数

题目：

class Solution {
    public int thirdMax(int[] nums) {
        int len  = nums..length;  //数组长度
        long first, second, third;
        first = second = third = Long..MIN_VALUE;  //定义前三的数字
        
        if (len <= 2) {
            return Math..max(nums[0], nums[len - 1]);  //数组长度不足3，直接返回最大值
        }
        for (int i = 0; i < nums..length; i++) {
            int cur = nums[i];
            if (cur == first || cur == second) {  
                continue;  //重复数值直接跳过
            }
            if (cur > first) {  //当前值大于最大值，重新给一二三赋值
                third = second;
                second = first;
                first = cur;
                continue;
            }
            if (cur > second) {  //当前值大于第二大的值，重新给二三赋值
                third = second;
                second = cur;
                continue;
            }
            if (cur > third) {  //当前值大于第三大的值，重新给三赋值
                third = cur;
            }
        }

        return third == Long..MIN_VALUE ? (int)first : (int)third;  //第三的值有改动就返回改动后的值，如果还是初始化的MIN_VALUE就返回最大值

    }
}

628.三个数的最大乘积

题目：

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays..sort(nums);
        int len = nums..length;
        if (nums[len-1] * nums[len-2] * nums[len-3] > nums[0] * nums[1] * nums[len-1])
            return nums[len-1] * nums[len-2] * nums[len-3];
        else
            return nums[0] * nums[1] * nums[len-1];
    }
}

2.2、统计数组中的元素

645.错误的集合

题目：

class Solution {
    public int[] findErrorNums(int[] nums) {
        int len = nums..length;
        int[] cnts = new int[len + 1];
        for (int x : nums) cnts[x]++;
        int[] ans = new int[2];
        for (int i = 1; i <= len; i++) {
            if (cnts[i] == 0) ans[1] = i;
            if (cnts[i] == 2) ans[0] = i;
        }
        return ans;
    }
}

697.数组的度

题目：

class Solution {
    int N = 50009;
    public int findShortestSubArray(int[] nums) {
        int n = nums..length;
        int[] cnt = new int[N];  //存放每个数字出现在的次数
        int[] first = new int[N], last = new int[N];  //记录每个数字的第一次出现的位置和最后出现的位置
        Arrays..fill(first, -1);
        int max = 0;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            max = Math..max(max, ++cnt[t]);  //遍历得到最大的度
            if (first[t] == -1) first[t] = i;  //记录第一次出现的位置
            last[t] = i;  //记录最后出现的位置；
        }
        int ans = Integer..MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            if (cnt[t] == max) ans = Math..min(ans, last[t] - first[t] + 1);
        }
        return ans;
    }
}

448.找到所有数组中消失的数字

题目：

// 数组记录法，需要额外数组记录数值是否出现
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int len = nums..length;
        int[] cnts = new int[len + 1];  //建立数组记录数值的出现
        Arrays..fill(cnts, 0);
        for (int n : nums) cnts[n]++;
        for (int i = 1; i < len + 1; i++){
            if (cnts[i] == 0) result..add(i);  //cnts[i]==0说明没有出现当前数值
        }
        return result;
    }
}

//哈希记录，在原数组进行记录，不实用额外空间
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int lenn = nums..length;
        for (int num : nums) {
            int x = (num - 1) % len;  // 原数组坐标是0-(len-1)，所以需要num-1；对数组长度取余
            nums[x] += len;  //加上数组长度后，所有出现过的数值的索引都会大于len
        }
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < len; i++) {
            if (nums[i] <= len) {  //小于len就说明该数值没有出现过，添加到ans
                ret..add(i + 1);
            }
        }
        return ans;
    }
}

442.数组中重复的数据

题目：

//排序后前后数值对比，重复的加入到结果中
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        Arrays..sort(nums);  //排序
        for (int i = 0; i < nums..length - 1; i++) {
            if (nums[i] == nums[i + 1]) result..add(nums[i]);  //对比，前后数值相同就加入到结果中
        }
        return result;
    }
}

//哈希标记
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int len = nums..length;
        for (int x : nums) {
            int y = (x - 1) % len;  //数组坐标是0-（len-1），所以减一除以长度就是该数值的索引
            nums[y] += len;  //数值索引位置的值加上数组长度
        }
        for(int i = 0; i < len; i++) {
            if (nums[i] > 2 * len) result..add(i + 1);  //如果数值出现两次，在上方就会加上了两次len，
        }
        return result;
    }
}

41.缺失的第一个正数

题目：

/*哈希表记录（参考力扣官方解析，来源：力扣（LeetCode））
	对于一个长度为N的数组，其中没有出现的最小正整数只能在[1,N+1] 中。这是因为如果[1,N] 都出现了，那么答案是N+1，否则答案是[1,N] 中没有出现的最小正整数。
	所以我们先将负数都设置为大于数组长度len的数，再将数值小于等于len的数的索引位置取负数，这样就可以再次遍历数组，第一个出现正数的数组下标加1就是最终结果。
*/
class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums..length;
        // 将负数都取大于len的数，我们取len+1
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
        }

        // 将小于等于len的元素对应的位置变为负数
        for (int i = 0; i < len; i++) {
            int num = Math..abs(nums[i]);
            if (num <= len) {
                nums[num - 1] = -Math..abs(nums[num - 1]);
            }
        }

        // 返回第一个大于0的元素下标+1
        for(int i = 0; i < len; i++) {
            if (nums[i] >= 0) return i + 1;
        }
        return len + 1;

    }
}

274.H指数

题目：

/*排序法
	将数组排序，并从大到小遍历，最初将h设为0，每次遍历的值大于h，就将h+1，直到h无法再增加。
*/
class Solution {
    public int hIndex(int[] citations) {
        Arrays..sort(citations);
        int h = 0;
        int i = citations..length - 1; 
        while (i >= 0 && citations[i] > h) {
            h++; 
            i--;
        }
        return h;
    }
}

/*数组计数
	根据题目可知h是一个不大于论文篇数n的数；建立一个数组来记录每个h的论文篇数。
*/
public class Solution {
    public int hIndex(int[] citations) {
        int n = citations..length;
        int total = 0;
        int[] counter = new int[n + 1];  //计数数组
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n) {  //因为h不大于论文篇数n，大于总篇数n的全部放在count[n]中
                counter[n]++;
            } else {
                counter[citations[i]]++;  //记录每个h的论文篇数
            }
        }
        for (int i = n; i >= 0; i--) {  //从大到小遍历
            total += counter[i];  //大于或等于当前引用次数i的总论文数
            if (total >= i) {
                return i;
            }
        }
        return 0;
    }
}

2.3、数组的改变、移动

453.最小操作次数使数组元素相等

题目：

/*排序法
	思路：本题正向思路是每次给n-1个元素+1，最少几次使得数组元素全部相等。我们可以反向思考一下，其实就是将最大的元素-1然后所有元素+1。
*/
class Solution {
    public int minMoves(int[] nums) {
        Arrays..sort(nums);
        int res = 0;
        for (int i = 0; i < nums..length; i++) {
            res += nums[i] - nums[0];
        }
        return res;
    }
}

283.移动零

class Solution {
    public void moveZeroes(int[] nums) {
        int len = nums..length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) {
                count++;  // 记录0的个数
                continue;
            }
            nums[i - count] = nums[i];  // 将非0数字往前移动
        }
        while (count > 0) {
            nums[len - count] = 0;  // 后面补0
            count --;
        }
    }
}

2.4、二维数组及滚动数组

118.杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {  // 前后添加1
                    row..add(1);
                }else {
                    row..add(ret..get(i - 1)..get(j - 1) + ret..get(i - 1)..get(j));
                }
            }
            ret..add(row);
        }
        return ret;
    }
}

119.杨辉三角II

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> C = new ArrayList<List<Integer>>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row..add(1);
                } else {
                    row..add(C..get(i - 1)..get(j - 1) + C..get(i - 1)..get(j));
                }
            }
            C..add(row);
        }
        return C..get(rowIndex);
    }
}

598.范围求和II

/*
* 本题可以用暴力解法，但是复杂度比较大
* 据题意，每次增加1都是从数组[0][0]开始，所以会有交集，最大整数肯定出现在数值[0][0]的这个交集中
*/
public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        for (int[] op: ops) {
            m = Math..min(m, op[0]);
            n = Math..min(n, op[1]);
        }
        return m * n;
    }
}

2.5、数组的旋转

189.旋转数组

题目：

// 直接暴力解法（超时），直接一个一个的移动
class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums..length;
        for (int i = 0; i < k; i++) {
            int num = nums[len-1];
            for (int j = len-1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = num;
        }
    }
}

// 数组反转（参考力扣官方解析）
// 基本步骤：先将数组整体翻转，在分别翻转前后两个部分
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums..length;
        reverse(nums, 0, nums..length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums..length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

操作	结果
原始数组	1 2 3 4 5 6 7
翻转所有元素	7 6 5 4 3 2 1
翻转[0, k mod n-1]区间的元素	5 6 7 4 3 2 1
翻转[k mod n, n-1]区间的元素	5 6 7 1 2 3 4

396.旋转函数

题目：

// 在上一题的基础上修改(超时)，每一翻转一个数，计算总和比大小。
class Solution {
    public int maxRotateFunction(int[] nums) {
        int len = nums..length;
        int max = 0;
        for (int i = 0; i < nums..length; i++) {
            max += i * nums[i];
        }
        for (int i = 1; i < nums..length; i++) {
            int sum = 0;
            reverse(nums, 0, nums..length - 1);
            reverse(nums, 1, nums..length - 1);
            for (int j = 0; j < nums..length; j++) {
                sum += j * nums[j];
            }
            if (sum > max) max = sum;
        }
        return max;
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

方法二：错位相减法

（作者：yixingzhang 链接：https://leetcode-cn.com/problems/rotate-function/solution/qian-lu-qi-qu-wang-wo-men-ke-yi-hu-xiang-iqax/](https://leetcode-cn.com/u/yixingzhang/)）

$$
F(k) = 0 * A[0] + 1 * A[1] + … + (n-1) * A[n-1] \
F(k+1) = 0 * A[n-1] + 1 * A[0] + 2 * A[1] + … + (n-1) * A[n-2] \
F(k+1) - F(k) = -(n-1) * A[n-1] + 1 * A[0] + 1 * A[1] + … + 1 * A[n-2] \
F(k+1) = F(k) - n * A[n-1] + 所有数的和 \
F(k+i) = F(k+i-1) - n * A[n-i] + 所有数的和
$$

// 用到了数学的错位相减，可能不一定能想到
class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums..length;
        int max = 0;
        int count = 0;
        // 统计数组所有数的和
        int sum = 0;
        // 计算 F(0) 的值
        for (int i : nums) {
            max += count++ * i;
            sum += i;
        }
        // 记录上一个计算结果
        int tmp = max;
        for (int i = 1; i < n; i++) {
            // 利用等差数列求解
            tmp = tmp + sum - n * nums[n - i];
            if (max < tmp) {
                max = tmp;
            }
        }
        return max;
    }
}

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

54.螺旋矩阵

题目：

/*
思路（参考力扣）：
	本题的数组循环不再是简单的双重选好就可以解决。可以看到仔细观察，这个循环的一个周期是什么，起止分别是什么：
	左上——》右上——》右下——》左下——》左上——》（第二个循环的左上）D:\Learning\PersonalBlog\CodeChenBlog\source/algo-arrayD:\Learning\PersonalBlog\CodeChenBlog\source/algo-arrayD:\Learning\PersonalBlog\CodeChenBlog\source/algo-array..
	这是一个完整的循环，所以依照这个思路写算法
*/
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        int rows = matrix..length, columns = matrix[0]..length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        if (matrix == null || matrix..length == 0 || matrix[0]..length == 0) {
            return res;
        }
        while (left <= right && top <= bottom) {
            // 左上——》右上
            for(int column = left; column <= right; column++){
                res..add(matrix[top][column]);
            }
            // 右上——》右下
            for(int row = top + 1; row <= bottom; row++){
                res..add(matrix[row][right]);
            }
   
            if (left < right && top < bottom) {
                // 右下——》左下
                for (int column = right - 1; column >= left; column--) {
                    res..add(matrix[bottom][column]);
                }
                // 左下——》左上
                for (int row = bottom - 1; row > top; row--) {
                    res..add(matrix[row][left]);
                }
            }
            // 四个边界都向中间收拢
            left++;
            right--;
            top++;
            bottom--;
        }
        return res;
    }
}

59.螺旋矩阵II

题目：

/*
	这个题和上一个题其实是一样的，上一个题给了一个二维数组，需要螺旋给出相应结果；本题需要自己螺旋的建立一个数组
*/
class Solution {
    public int[][] generateMatrix(int n) {
        int num = 1;
        int[][] matrix = new int[n][n];
        int left = 0, right = n - 1, top = 0, bottom = n - 1;

        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                matrix[top][column] = num;
                num++;
            }
            for (int row = top + 1; row <= bottom; row++) {
                matrix[row][right] = num;
                num++;
            }

            if (left < right && top < bottom) {
                for (int column = right -1; column >= left; column--) {
                    matrix[bottom][column] = num;
                    num++;
                }
                for (int row = bottom - 1; row > top; row--) {
                    matrix[row][left] = num;
                    num++;
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return matrix;
    }
}

498.对角线遍历

题目：

/*
（参考力扣官方解析）
*/
class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {

        // 检查是否为空
        if (matrix == null || matrix..length == 0) {
            return new int[0];
        }
        
        int N = matrix..length;
        int M = matrix[0]..length;
        int row = 0, column = 0;

        // 设定标志位来确定对角线走向，向上走还是向下走
        int direction = 1;
        
        int[] result = new int[N*M];
        int r = 0;
        
        while (row < N && column < M) {
            
            result[r++] = matrix[row][column];

            // 通过判断对角线走向来给row和column进行加或减
            int new_row = row + (direction == 1 ? -1 : 1);
            int new_column = column + (direction == 1 ? 1 : -1);

            // 判断是否是对角线走向最后一个元素 
            if (new_row < 0 || new_row == N || new_column < 0 || new_column == M) {

                if (direction == 1) {
                    row += (column == M - 1 ? 1 : 0) ;
                    column += (column < M - 1 ? 1 : 0);

                } else {
                    column += (row == N - 1 ? 1 : 0);
                    row += (row < N - 1 ? 1 : 0);
                }

                // 转向
                direction = 1 - direction;

            } else {

                row = new_row;
                column = new_column;
            }
        }
        return result;
    }
}

2.7、二维数组变换

566.重塑矩阵

题目：

/*
解法一：
*/
class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int M = mat..length;
        int N = mat[0]..length;
        
        // 输出不合理，返回原数组
        if (M * N != r * c) {
            return mat;
        }
        
        // 创建结果数组
        int[][] res = new int[r][c];
        int row = 0, col = 0;
        
        // 遍历原数组
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                // 控制结果数组的换行，当col到最后一列时就换行，将row+1换行，col置0，重新从第一列第row+1行开始存数据
                if (col == c) {
                    row += 1;
                    col = 0;
                }
                res[row][col] = mat[i][j];
                col += 1;
            }
        }
        return res;
    }
}

/*
解法二(力扣官方解析):主要就是在存储数据时用了数学的除和取余，可能一般不一定能想到，思想和解法一是类似的，都是以列为基准来控制换行，取余就是列在递增，除整就是控制换行
*/
class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat..length;
        int n = mat[0]..length;
        if (m * n != r * c) {
            return mat;
        }

        int[][] ans = new int[r][c];
        for (int x = 0; x < m * n; ++x) {
            ans[x / c][x % c] = mat[x / n][x % n];
        }
        return ans;
    }
}

48.旋转图像

题目：

/*
参考力扣官方解析
*/
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix..length;
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

73.矩阵置零

题目：

/*
参考：
作者：powcai
链接：https://leetcode-cn..com/problems/set-matrix-zeroes/solution/o1kong-jian-by-powcai/
来源：力扣（LeetCode）

这么版本较好理解
解析：主要需要想到将第一行和第一列作为标志位，最后的置零就通过第一行和第一列来判断是否置零。
	1、设置两个标志记录第一行和第一列是否存在0
	2、遍历除第一行和第一列元素，如果是0就将对应的第一行和第一列元素置零
	3、最后通过第一行和第一列为0的对应行和列置零
	4、第一步的两个标志如果是第一行和第一列原始数据就存在0，就需要将第一行或（和）第一列置零
*/
class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix..length;
        int col = matrix[0]..length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        // 第一行是否有零
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                row0_flag = true;
                break;
            }
        }
        // 第一列是否有零
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                col0_flag = true;
                break;
            }
        }
        // 把第一行第一列作为标志位
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 置0
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (row0_flag) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0_flag) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        } 
    }
}

2.8、前缀和数组

303.区域和检索-数据不可变

题目：

/*
解析：主要在数据处理时就将每一个数的前缀和求出，并存储起来，最后简单计算返回结果即可
*/
class NumArray {
    int[] sums;

    public NumArray(int[] nums) {
        int n = nums..length;
        sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return sums[right + 1] - sums[left];
    }
}

304.二维区域和检索 - 矩阵不可变

题目：

/*
解析：本题思路和上一题一样，需要处理数据，存储所有的前缀和，但是二维数据计算前缀和会复杂一点。需要将整体和一些局部相加减。
*/ 
class NumMatrix {
    int[][] sums;

    public NumMatrix(int[][] matrix) {
        int m = matrix..length;
        if (m > 0) {
            int n = matrix[0]..length;
            sums = new int[m + 1][n + 1];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 当前格子的和 = 上方的格子的和 + 左边的格子的和的 - 左上角的格子的和 + 当前格子的值[和是指对应的前缀和，值是指原数组中的值]
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
}

238.除自身意外数组的乘积

题目：

/*
作者：LeetCode-Solution
链接：https://leetcode-cn..com/problems/product-of-array-except-self/solution/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode-/
来源：力扣（LeetCode）

解析：简单的使用双重循环求结果会超时，所以需要优化。
为了减少计算次数，我们需要将每次计算结果存储，每次就只需要乘一次。
建立一个数组answer，存结果。首先从左遍历原数据，将左边的数据相乘存储在answer中，从而得到所有的左边乘积。
再在answer中从右边开始遍历，设定一个变量存储右边的乘积，每次将右边的乘积乘以左边的乘积answer[i]，最后得到的answer就是结果
*/

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

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= nums[i];
        }
        return answer;
    }
}