时间戳

首页 > 解决方案 > 找出四倍的数量，使它们加起来为一个特定的总和

algorithm - 找出四倍的数量，使它们加起来为一个特定的总和

问题描述

给定一个正整数数组，您要找到 i < j < k < l 的四元组 (i,j,k,l) 的数量，使得它们加起来为 T，其中 T 是给定的。T < 1+10^6 和 N < 5001

这个问题似乎通常被称为四和或四和。

问题在于以下代码在 CodeChef 上的 ayush_ar0204 解决方案中循环遍历数组（s 是数组）：

    sort(s,s+n);

    for (long long k=2;k<(n-1);++k){
        if (s[k] >= t)
            break;  

        long long j=k-1;
        for(long long i=0;i<j;++i){
            if(s[i]+s[j]<t){
                ++counts[s[i]+s[j]];
            }
            else{
                i=j;
            }
        }
        for(long long l=k+1;l<n;++l){
            if ((t-(s[k]+s[l]))>=0){
                answer+=counts[t-(s[k]+s[l])];
            }
            else{
                l=n;
            }
        }
    }

检查第 21 行。它说 j=k-1。现在，我们正在为 i,k,l 操作循环。我们不是只检查四元组 (i,k-1,k,l) 而不是 (i,j,k,l) 吗？代码运行良好，但对我来说在逻辑上看起来不正确。

标签： algorithm

解决方案

该解决方案将运行时间从简单的 O(n 4 ) 减少到 O(n 2 )。它看起来有些奇怪，因为它重用了以前计算的信息。

在任何时候，我们都希望counts[m]（counts作为字典）包含这样的(i, j)对i < j < k数s[i] + s[j] == m。这在循环开始之前是非常正确的k == 1，因为没有对(i, j)所以每个计数都是 0。每次k增加，我们必须添加到计数中的唯一对是具有 的对j == k - 1。如果j < k - 1，则该对已在循环的最后一次迭代中计算在内。使用counts数组意味着我们不再查看特定的四元组(i, j, k, l)；相反，对于 的每个值，k我们遍历所有可能的值，并将具有正确总和l的有效元组的存储计数添加到总数中。(i, j)

推荐阅读