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

Question

我们需要找出一个数组中是否存在4个数字a、b、c和d(所有数字应该在不同的索引处)，其总和等于常数k。

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

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

他们的代码:

    // 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

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

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

现在考虑这对 (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) .

由于第二个循环遍历所有对，因此对 (a, b)必须访问过，并且必须检测到四重奏。因此该算法是正确的。