資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢陣列中四個元素 a、b、c 和 d，使得 a+b = c+d
假設我們有一個整數列表。我們的任務是找到四個不同的整數作為兩對，例如 (a, b) 和 (c, d)，使得 a+b = c+d。如果有多個答案，則只打印一個。假設陣列元素如下：A = [7, 5, 9, 3, 6, 4, 2]，則對可以是 (7, 3) 和 (6, 4)
這裡我們將使用雜湊技術。我們使用和作為鍵，對作為雜湊表中的值。我們必須遵循以下步驟來解決此問題。
- 對於 i 從 0 到 n – 1，執行
- 對於 j 從 i + 1 到 n – 1，執行
- 找到和
- 如果雜湊表中已經存在該和，則列印先前的對和當前對
- 否則，更新雜湊表。
- 對於 j 從 i + 1 到 n – 1，執行
示例
#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)
更新於： 2019年12月19日
640 次檢視
廣告