电商网站开发难点,咨询类网站建设,台州做网站app的公司,腾讯云 安装 wordpress题目链接 文章目录 1. 思路讲解1.1 dp表的创建1.2 状态转移方程1.3 使用哈希表找到k1.4 初始化1.5 返回值1.6 该题坑爹的一点 2. 代码编写 1. 思路讲解
我们要知道以某个位置为结尾的子序列的数量#xff0c;可以通过它的以上一位置的为结尾的子序列的数量得知#xff0c;也…题目链接 文章目录 1. 思路讲解1.1 dp表的创建1.2 状态转移方程1.3 使用哈希表找到k1.4 初始化1.5 返回值1.6 该题坑爹的一点 2. 代码编写 1. 思路讲解
我们要知道以某个位置为结尾的子序列的数量可以通过它的以上一位置的为结尾的子序列的数量得知也就是说这是一个dp问题。
1.1 dp表的创建
dp问题我们需要创建dp表如果我们单纯使用dp[i]来表示以 i 位置为结尾的子序列的数量是完全不够的。因为我们不知道以 i-1 位置为结尾的等差数列是怎样的它的公差是几我们是不知道的。也就是说我们不确定 i 位置的元素是否能跟到以 i - 1 位置为结尾的数列的后面。
但是如果知道了数列的后两个元素也就是知道了 i - 1 位置以及数列中上一个位置的元素就能知道数列的公差了也就能知道 i 位置的元素是否能跟到后面了所以我们需要用两个元素来表示每个dp位置。
创建二维dp表dp[i][j]表示以 i 位置的元素为数列倒数第二个元素以 j 位置的元素为数列倒数第一个元素为结尾的数列数量有多少。我们人为规定i j
1.2 状态转移方程
nums[j] - nums[i]可以得到公差再由 num[i] - 公差 可以得到上一项的值记为 a我们需要知道这个 a 值在nums中是否存在且是否在 i 位置的前面两个条件都满足才符合题意。
记 a 在nums中的下标为k至于怎么找到这个k下面会说我们要找到以 i 和 j 位置为结尾的等差数列的个数其实找到所有 k 和 i 位置元素结尾的等差数列的个数相加即可a元素在nums中的位置不只一个那么k可能就不只一个。并且也需额外加上一个数列就是 ki j本身所构成的等差数列。
那么状态转移方程就为dp[i][j] dp[k][i] 1
1.3 使用哈希表找到k
我们写代码的时候遍历所有 i 和 j 的组合时间复杂度就已经到达 N^2 了如果此时再在数组中去寻找 k 那么时间复杂度就 N^3了这大概率是会超时的。
我们可以在dp之前使用哈希表去将所有元素数组下标绑定在一起放在哈希表中这样我们得到了 a 之后就可以使用哈希表很快地查找到 k 了。
1.4 初始化
刚开始以 ij 位置为结尾只有两个元素不符合题目中的等差数列可以记为 0 所以我们初始化的时候将dp表中所有的值初始化为 0 即可。又因为vector会默认初始化为0所以我们不用手动初始化了。
1.5 返回值
我们要求的是所有的等差数列所以我们要将所有符合题意的dp[i][j]都加起来然后返回。
1.6 该题坑爹的一点
虽然题目已经说了返回值以及各个元素的值都在int范围内但是我们求a的时候a的值可能会超出int的范围从而出错所以我们将a的类型要设置为long long。然后用a查找k用的是hash所以hash的第一个类型也要为long long。
2. 代码编写 class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {int n nums.size();// 创建哈希表便于很快地找到k// 因为k不只一个所以用vector来存储unordered_maplong long, vectorint hash;for (int i 0; i n; i) hash[nums[i]].push_back(i);// 创建二维dp表第一维为数列的倒数第二个元素第二维为数列的倒数第一个元素vectorvectorint dp(n, vectorint(n));int ret 0; // 所有数组的数量// i为nums第0个位置时不管j为几dp[0][j]都为0因为只有两个元素// 所以从第1个位置开始填表即可且i一定不为nums最后一个元素for (int i 1; i n - 1; i){// j从i1开始一直到最后一个位置寻找符合题意的情况for (int j i 1; j n; j){long long a (long long)2*nums[i] - nums[j];if (hash.count(a)) // 看a是否存在于hash中{// 如果存在遍历a对应的vectorfor (auto k : hash[a]){// k需要小于iif (k i) dp[i][j] dp[k][i] 1;}} ret dp[i][j];}}return ret;}
};
