在数组中找到四个元素a,b,c和d,以便在C ++中a + b = c + d

假设我们有一个整数列表。我们的任务是找到四个不同的整数,分别为(a,b)和(c,d)两对,这样a + b = c + d。如果有多个答案,则仅打印一个。假设数组元素像:A = [7,5,9,3,6,4,2],那么对可以是(7,3)和(6,4)

在这里,我们将使用哈希技术。我们使用总和作为键,作为哈希表中的值对。我们必须按照以下步骤解决此问题。

  • 对于0到n – 1范围内的i

    • 求和

    • 如果哈希表已经有总和,则打印前一对和当前对

    • 否则,更新哈希表。

    • 对于i +1至n – 1范围内的j

    示例

    #include<iostream>
    #include<map>
    using namespace std;
    bool getTwoPairs(int arr[], int n) {
       map<int, pair<int, int> > hash_table;
       for (int i = 0; i < n; ++i) {
          for (int j = i + 1; j < n; ++j) {
             int sum = arr[i] + arr[j];
             if (hash_table.find(sum) == hash_table.end())
                hash_table[sum] = make_pair(i, j);
             else {
                pair<int, int> pp = hash_table[sum];
                cout << "(" << arr[pp.first] << " + " << arr[pp.second] << ") = (" << arr[i] << " + " << arr[j] << ")";
                return true;
             }
          }
       }
       cout << "No pairs found";
       return false;
    }
    int main() {
       int arr[] = {7, 5, 9, 3, 6, 4, 2};
       int n = sizeof arr / sizeof arr[0];
       cout << "The pairs are: ";
       getTwoPairs(arr, n);
    }

    输出结果

    The pairs are: (7 + 4) = (5 + 6)