当前位置:首页 > 编程笔记 > 正文
已解决

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

来自网友在路上 177877提问 提问时间:2023-10-07 22:09:42阅读次数: 77

最佳答案 问答题库778位专家为你答疑解惑

解题步骤:

参考代码:

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size();//把元素和它对应的所有下标绑定存放到哈希表中unordered_map<double,vector<int>> hash;for(int i=0;i<n;i++){hash[nums[i]].push_back(i);}//dp表的值全是0,无需初始化//填表vector<vector<int>> dp(n,vector<int>(n));int ret=0;for(int j=2;j<n;j++){for(int i=1;i<j;i++){double b=nums[i];double c=nums[j];double a=2*b-c;if(hash.count(a)){for(const auto& k:hash[a]){//符合题意的k对应的dp[k][i]都要加等到dp[i][j]上if(k<i){dp[i][j]+=dp[k][i]+1;}//后面的下标一定都是大于等于i的else{break;}}//统计次数ret+=dp[i][j];}}}//返回值return ret;}
};

你学会了吗???

查看全文

99%的人还看了

猜你感兴趣

版权申明

本文"力扣 -- 446. 等差数列划分 II - 子序列":http://eshow365.cn/6-16968-0.html 内容来自互联网,请自行判断内容的正确性。如有侵权请联系我们,立即删除!