算法每日一题——第一天——统计特殊四元组

方法一：枚举法

依次遍历每一种可能，这个方法比较简单，直接上代码

int countQuadruplets(int* nums, int numsSize)
{
    int count=0;
    int a,b,c,d;
    for(a=0;a<numsSize-3;a++)
    {
        for(b=a+1;b<numsSize-2;b++)
        {
            for(c=b+1;c<numsSize-1;c++)
            {
                for(d=m+1;d<numsSize;d++)
                {
                    if(nums[a] + nums[b] + nums[c] == nums[d])
                    {
                        count++;
                    }
                }  
            }
        }
    }
    return count;
}

空间复杂度：

时间复杂度：O(1)

方法二：哈希表法

(1)

(2)要满足上式，nums[d] - nums[c] 一定大于零 ，当nums[d] - nums[c] 大于零时，我们用哈希表统计它出现的次数即  cnt[nums[d] - nums[c]]++  (cnt为创建的哈希表)。

(3)当我们在遍历a，b时，若满足 nums[a] + nums[b] == nums[d] - nums[c]时，说明符合题意，由于我们上面已经将 nums[d] - nums[c] 出现次数统计，在这里我们只需要 ：

count+=cnt[nums[d] - nums[c]]

(4)在枚举时，我们可以采用逆序枚举，我们首先要统计c，d，我们可以先枚举 b 从而缩小c，d的范围，1 <= b < c < d < numsSize ,接下来要让每一个c，d都被枚举到，我们可以枚举d，在枚举b时，让c=b+1,也相当于枚举了一遍。

上代码：

int countQuadruplets(int* nums, int numsSize)
{
    int count =0;
    int cnt[201]={0};
    int a,b,c,d;
    for(b=numsSize-3;b>=1;b--)
    {
        for(d=b+2;d<numsSize;d++)
        {
            if(nums[d]>=nums[b+1])
            {
                cnt[nums[d]-nums[b+1]]++;
            }
        }
        for(a=0;a<b;a++)
        {
            count+=cnt[nums[a]+nums[b]];
        }
    }
    return count;
}

时间复杂度:

空间复杂度:    (C是nums[i]的最大取值)