給你一個 下標從 0 開始 的整數陣列 nums ，回傳滿足下述條件的 不同 四元組 (a, b, c, d) 的 數目 ：
nums[a] + nums[b] + nums[c] == nums[d] ，且
a < b < c < d
鏈接：1995.統計特殊四元組
解題思路：
暴露破解一：
class Solution {
public:
int countQuadruplets(vector<int>& nums) {
int n= nums.size();
int s=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++)
for(int k=j+1;k<n;k++){
int sum=nums[i]+nums[j]+nums[k];
for(int z=k+1;z<n;z++){
if(sum==nums[z]) s++;
}
}
}
return s;
}
};
使用哈希表進行保存c后面d的個數：
nums[a]+nums[b]+nums[c]=nums[d]
a<b<c<d
class Solution {
public:
int countQuadruplets(vector<int>& nums) {
int n= nums.size();
int s=0;
unordered_map<int,int>ma;
//統計2~n-1,中間數字的個數,C的列舉也是從后往前面推
//C只能從n-2開始取，n-1是屬于D
for(int i=n-2;i>=2;i--){
ma[nums[i+1]]++;//這里也就是統計d范圍之內數的個數
for(int j=0;j<i;j++){
for(int k=j+1;k<i;k++){
int su=nums[i]+nums[j]+nums[k];
s+=ma[su];
}
}
}
return s;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/401577.html
標籤：其他
上一篇：2021年度總結
下一篇：試題 基礎練習 字母圖形