查找未通过 4 和问题代码的测试用例

Question

求一个数组中是否存在a、b、c、d这4个数（所有数的下标不同），其和等于常数k。

现在它的基于散列的解决方案是这样的：创建一个散列，其键作为数组中每对的总和，值作为索引对的数组，其总和是键。现在遍历数组中的每一对，并尝试在我们创建的散列 table 中找到剩余的总和，同时还要检查没有 2 个索引应该是共同的。

虽然上面的解决方案很好，但我在 geeksforgeeks.com 上看到的一个解决方案是这样做的：在散列 table 中，值是一对而不是对数组。它仅存储以总和结尾的最后一对。它显然对我来说是错误的，但我仍然找不到失败的测试用例。

他们的代码：

    // A hashing based  CPP program to find if there are    
    // four elements with given sum. 
    #include <bits/stdc++.h>     
    using namespace std; 

    // The function finds four elements with given sum X     
    void findFourElements (int arr[], int n, int X)    
    {     
        // Store sums of all pairs in a hash table    
        unordered_map<int, pair<int, int>> mp;     
        for (int i = 0; i < n-1; i++)     
            for (int j = i+1; j < n; j++)    
                mp[arr[i] + arr[j]] = {i, j};      

        // Traverse through all pairs and search     
        // for X - (current pair sum).      
        for (int i = 0; i < n-1; i++)     
        {     
            for (int j = i+1; j < n; j++)     
            {     
                int sum = arr[i] + arr[j];     
          
                // If X - sum is present in hash table,                 
                if (mp.find(X - sum) != mp.end())     
                {               
                    // Making sure that all elements are     
                    // distinct array elements and an element 
                    // is not considered more than once.     
                    pair<int, int> p = mp[X - sum];     
                    if (p.first != i && p.first != j &&     
                            p.second != i && p.second != j)     
                    {     
                        cout << arr[i] << ", " << arr[j] << ", "     
                             << arr[p.first] << ", "     
                             << arr[p.second];     
                        return;     
                    }     
                }     
            }     
        }     
    }     
          
    // Driver program to test above function     
    int main()     
    {     
        int arr[] = {10, 20, 30, 40, 1, 2};     
        int n = sizeof(arr) / sizeof(arr[0]);     
        int X = 91;     
        findFourElements(arr, n, X); 
        return 0; 
    }

如何找到此代码失败的测试用例，或者如果它是正确的，如何找到？

Answer 1

It only stores the last pair which concludes to a sum.

不完全是。它存储所有对，就像您存储所有长度为 2 的数组一样。他们的算法在此处执行此操作：

// Store sums of all pairs in a hash table 
unordered_map<int, pair<int, int>> mp; 
for (int i = 0; i < n-1; i++) 
    for (int j = i+1; j < n; j++) 
        mp[arr[i] + arr[j]] = {i, j};

{i, j} 是一对，第一个值是 i，第二个值是 j。

我认为你对这里发生的事情感到困惑：

pair<int, int> p = mp[X - sum]; 
if (p.first != i && p.first != j && 
        p.second != i && p.second != j)

他们正在从地图中拉出一对。值得注意的是，他们匹配的那对形成 X 总和。他们可以做：

if (mp[X - sum].first != i && mp[X - sum].first != j && mp[X - sum].second != i && mp[X - sum].second != j)

但这既丑陋又需要大量地图查找。因此，他们决定在局部变量 p.
中复制他们关心的对
然后他们确保 p 中的索引都不是他们现在正在查看的索引，i 和 j。这有意义吗？

Answer 2

算法正确。考虑满足以下条件的四元组 (a, b, c, d)： (1) arr[a] + arr[b] + arr[c] + arr[d] == k； (2) a < b < c < d.

显然，当且仅当存在这样的四元组 (a, b, c, d) 时，数组的四个不同元素总和为 k。

现在考虑 (a, b) 对。您提到程序记录了最后一对 (e, f) (e < f)，这是对 (a, b)（即 arr[a] + arr[b] + arr[e] + arr[f] == k）的恭维。请注意，由于 (e, f) 是具有此类属性的最后一对，因此 e >= c。因此a < b < e < f。现在我们找到了一个有效的四元组 (a, b, e, f).

由于第二个循环遍历了所有的pair，所以pair (a, b)肯定已经被访问过，四元组也一定被检测到了。所以算法是正确的。

查找未通过 4 和问题代码的测试用例

Finding a testcase which fails the code in the 4 sum problem

c++

hashtable

multimap