LeetCode刷题——446. 等差数列划分 II - 子序列

• 面试刷题第12天
• • LeetCode刷题——446. 等差数列划分 II - 子序列
  • • 1、题目描述
    • 2、解题思路

给你一个整数数组 nums ，返回 nums 中所有等差子序列的数目。
如果一个序列中至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。
（1）例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。
（2）再例如，[1, 1, 2, 5, 7] 不是等差序列。
数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。
例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。
题目数据保证答案是一个 32-bit 整数。

将数组的每一个位置都生成一张表，用来记录每一个以该位置结尾的产生的所有的差值的子序列数组的个数。
例如：数组[1，3，5，7]，以整数1位置结尾的产生的所有可能差值为0；
（1）以整数3结尾的，差值为2的数为1个，即[1，3]，再加上以1结尾的差值为2的，最终还是[1，3]。
（2）以整数5结尾的，差值为2的数为1个，即[3，5]，再加上以3结尾的差值为2的，最终是[3，5]、[1，3，5]；差值为4的数为1个，即[1，5]，再加上以1结尾的差值为4的，最终还是[1，5]；
（3）以整数7结尾的，差值为2的数为1个，即[5，7]，再加上以5结尾的差值为2的，即[3，5，7]，再加上以3结尾的差值为2的，即[1，3，5，7]，再加上以1结尾的差值为2的，最终结果是[5，7]、[3，5，7]、[1，3，5，7]；差值为4的数为1个，即[3，7]，再加上以3结尾的差值为4的，结果还是[3，7]。
（4）所以最终长度大于2的，有[1，3，5]、[1，3，5，7]、[3，5，7]。
Java代码如下：

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int ans = 0;
        ArrayList> maps = new ArrayList<>();
        for(int i=0; i
            //每一个位置都生成一张表
            maps.add(new HashMap<>());
            for(int j=i-1; j>=0; j--){
                long diff = (long) nums[i] - (long) nums[j];
                //若i位置和j位置的差值超过界限，肯定不存在一个长度大于2的等差数列
                if(diff <= Integer.MIN_VALUE || diff >= Integer.MAX_VALUE){
                    continue;
                }
                int dif = (int)diff;
                //j位置上差值为dif的子序列个数
                int count = maps.get(j).getOrDefault(dif, 0);
                ans += count;
                //i位置上差值为dif的子序列个数+count+1
                maps.get(i).put(dif, maps.get(i).getOrDefault(dif, 0) + count + 1);
            }
        }
        return ans;
    }
}