classSolution{public:intnumberOfArithmeticSlices(vector<int>&nums){constintn=nums.size();intans=0;// dp[i][j] := # of subseqs end w/ nums[j] nums[i]vector<vector<int>>dp(n,vector<int>(n));unordered_map<long,vector<int>>numToIndices;for(inti=0;i<n;++i)numToIndices[nums[i]].push_back(i);for(inti=0;i<n;++i)for(intj=0;j<i;++j){constlongtarget=nums[j]*2L-nums[i];if(numToIndices.count(target))for(constintk:numToIndices[target])if(k<j)dp[i][j]+=(dp[j][k]+1);ans+=dp[i][j];}returnans;}};
classSolution{publicintnumberOfArithmeticSlices(int[]nums){finalintn=nums.length;intans=0;// dp[i][j] := # of subseqs end w/ nums[j] nums[i]int[][]dp=newint[n][n];Map<Long,List<Integer>>numToIndices=newHashMap<>();for(inti=0;i<n;++i){numToIndices.putIfAbsent((long)nums[i],newArrayList<>());numToIndices.get((long)nums[i]).add(i);}for(inti=0;i<n;++i)for(intj=0;j<i;++j){finallongtarget=nums[j]*2L-nums[i];if(numToIndices.containsKey(target))for(finalintk:numToIndices.get(target))if(k<j)dp[i][j]+=(dp[j][k]+1);ans+=dp[i][j];}returnans;}}