等差数列Tag

由于在大厂笔试中多次出现等差数列的相关问题，所以在这里专门记录等差数列相关的笔试题，包括：
判断能否形成等差数列
最长等差数列
等差数列划分

等差数列

1.判断能否形成等差数列

题目

给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
示例 1：
1
2
3
输入：arr = [3,5,1]
输出：true
解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
示例 2：
1
2
3
输入：arr = [1,2,4]
输出：false
解释：无法通过重新排序得到等差数列。
提示：
- 2 <= arr.length <= 1000
- -10^6 <= arr[i] <= 10^6

思路

第一种思路比较直观，先对数组进行排序，然后根据第一项和第二项得到公差 d，接下来只需要循环判断 arr[i + 1] == arr[i] + d ? 即可。

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        if (arr.length <= 2) {
            return true;
        }
        Arrays.sort(arr);
        int d = arr[1] - arr[0];
        for (int i = 1; i < arr.length - 1; i++) {
            if (arr[i] + d != arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
}

很明显，因为先对数组进行排序，所以时间复杂度为 O(nlogn)
- 其实可以在 O(n) 的时间复杂度就完成本题。

第二种思路：

首先遍历数组，得到最小值和最大值，如果最小值等于最大值，说明数组中的元素都相同，是等差数列。
否则：
计算最大值和最小值的差值 diff = max - min，除以 n - 1，得到公差 d：
- 如果 d 不是整数，那就不是等差数列。
- 如果 d 是整数，再进行后续的操作。
每遍历到一个数，先判断其与最小值的差 arr[i] - min 是否能被 d 整除：
- 如果不能，那肯定不是等差数列。
- 否则就计算其 “下标” (arr[i] - min) / d，然后通过一个辅助数组 appeared 来判断这个数是否出现过，如果出现过，说明数组中出现了相同的元素，那就不是等差数列。否则继续遍历下一个数，直到数组遍历完。

class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int n = arr.length;
        if (n <= 2) {
            return true;
        }
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 得到数组的最大值和最小值
        for (int i = 0; i < n; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        if (min == max) {
            // 说明数组中元素都相同
            return true;
        }
        int diff = max - min;
        if (diff % (n - 1) != 0) {
            // 公差如果不为整数，那肯定不是等差数列
            return false;
        }
        int d = diff / (n - 1);
        boolean[] appeared = new boolean[n];
        for (int i = 0; i < n; i++) {
            if ((arr[i] - min) % d != 0) {
                // 如果当前元素和min的差不能被d整除
                return false;
            }
            int index = (arr[i] - min) / d;
            if (appeared[index]) {
                // 如果当前这个元素之前已经出现过了
                return false;
            } else {
                // 将这个元素标记为出现过
                appeared[index] = true;
            }
        }
        return true;
    }
}

时间复杂度为 O(n)

2.最长等差数列

题目

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
示例 1：
1
2
3
4
输入：nums = [3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。
示例 2：
1
2
3
4
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：
1
2
3
4
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。
提示：
- 2 <= nums.length <= 1000
- 0 <= nums[i] <= 500

思路

等差数列，有个核心概念就是公差。本题要求的是数组中最长等差子序列的长度，可以很容易推断出这存在重叠子问题，因此可以用动态规划来解决。

动归五部曲：

确定 dp 数组及下标含义：
- 我们定义 dp[i][d] 表示对于数组中的前 i+1 个数，当公差为 d 时，数组的最长等差子序列的长度是多少。
确定递推公式：
- 对于当前的数 nums[i]，它和之前的数的公差可能都不相同，因此，在内循环中，我们需要先计算当前数 nums[i] 和之前的数 nums[j] 的差值，以这个差值为公差去更新 dp 数组。
- 递推公式为：dp[i][d] = Math.max(dp[i][d], dp[j][d] + 1)
对 dp 数组进行初始化：
- 对于每轮循环，都将 dp[i] 初始化为 1，Arrays.fill(dp[i], 1)，表示不论公差为几，一开始的最长等差子序列长度为 1，即每个数自己就是一个等差数列。
确定迭代顺序：
- 很显然，外循环是遍历整个数组，从左到右进行遍历。内循环是遍历当前数 num[i] 之前的数，从左到右进行遍历。
举例推导 dp 数组。

最终代码如下：

class Solution {
    public int longestArithSeqLength(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 得到数组中的最大最小数
        for (int i = 0; i < n; i++) {
            if (nums[i] < min) {
                min = nums[i];
            }
            if (nums[i] > max) {
                max = nums[i];
            }
        }
        int diff = max - min;
        // dp[i][d] 表示前i+1个数，在公差为d时的最长等差子序列的长度
        int[][] dp = new int[n][2 * diff + 1];
        int res = 1;
        for(int i = 0; i < n; i++){
            Arrays.fill(dp[i],1);
            for(int j = 0; j < i; j++){
                int d = nums[i] - nums[j] + diff;
                dp[i][d] = Math.max(dp[i][d], dp[j][d] + 1);
                res = Math.max(res, dp[i][d]);
            }
        }
        return res;
    }
}

由于公差最小值为 -(max - min)，最大值为 (max - min)，所以 dp 数组二维的长度为 2 * (max - min) + 1。

3.等差数列划分

题目

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
- 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1：
1
2
3
输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2：
1
2
输入：nums = [1]
输出：0
提示：
- 1 <= nums.length <= 5000
- -1000 <= nums[i] <= 1000

思路

令 dp[i] 表示从 nums[0] 到 nums[i] 且以 nums[i] 为结尾的等差数列子数组的数量。则如果 num[i] 能够加入 num[i - 1] 所在的等差数列，dp[i] = dp[i - 1] + 1。

然后在遍历数组的过程中，将所有等差数列子数组的个数累计即可。

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return 0;
        }
        int n = nums.length;
        // dp[i]表示从nums[0]到nums[i]且以nums[i]为结尾的等差数列子数组的数量
        int[] dp = new int[n];
        // dp[i] = dp[i - 1] + 1, if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])
        int res = 0;
        for (int i = 2; i <n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) { 
                dp[i] = dp[i - 1] + 1;
            }
            res += dp[i];
        }
        return res;
    }
}