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

Categories:

题目描述
思路分析
1. 解法一：哈希 DP（推荐）
相似题目

题目描述

✅ 446. 等差数列划分 II - 子序列

思路分析

解法一：哈希 DP（推荐）

核心思路：

dp[i][diff] 表示以 i 结尾、公差为 diff 的长度≥2 子序列数量。

枚举 j < i，将 dp[j][diff] 累加到结果中并更新 dp[i][diff]。

新增长度为 2 的序列计入 dp[i][diff]。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示数组长度。

空间复杂度：O(n^2)，用于哈希表存储差值。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        Map<Long, Integer>[] dp = new Map[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }

        long res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long diff = (long) nums[i] - nums[j];
                int count = dp[j].getOrDefault(diff, 0);
                res += count;

                dp[i].put(diff, dp[i].getOrDefault(diff, 0) + count + 1);
            }
        }

        return (int) res;
    }
}

func numberOfArithmeticSlices(nums []int) int {
	n := len(nums)
	dp := make([]map[int64]int, n)
	for i := 0; i < n; i++ {
		dp[i] = make(map[int64]int)
	}

	res := 0
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			diff := int64(nums[i]) - int64(nums[j])
			count := dp[j][diff]
			res += count
			dp[i][diff] = dp[i][diff] + count + 1
		}
	}

	return res
}

相似题目

题目	难度	考察点
1027. 最长等差数列	中等	动态规划
1218. 最长定差子序列	中等	动态规划
673. 最长递增子序列的个数	中等	动态规划
300. 最长递增子序列	中等	动态规划
446. 等差数列划分 II - 子序列	困难	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/18286390