leetcode打卡第一天

给你一个 下标从 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;
    }
};