C++巧用哈希表：高效找出和为指定值且差值最小的两数

这个问题可以通过使用哈希表（unordered_set）来高效解决。我们可以在遍历数组时，检查当前元素与目标值n的差值是否已经存在于哈希表中。如果存在，则说明找到了两个数，它们的和等于n。否则，将当前元素插入哈希表中。 以下是C++代码实现： ```cpp #include <iostream> #include <unordered_set> #include <vector> #include <algorithm> using namespace std; pair<int, int> findPairWithSum(const vector<int>& nums, int n) { unordered_set<int> seen; pair<int, int> result = {-1, -1}; int minDiff = INT_MAX; for (int num : nums) { int complement = n - num; if (seen.find(complement) != seen.end()) { int currentDiff = abs(num - complement); if (currentDiff < minDiff) { minDiff = currentDiff; result = {min(num, complement), max(num, complement)}; } } seen.insert(num); } return result; } int main() { int n, m; cin >> n >> m; vector<int> nums(m); for (int i = 0; i < m; ++i) { cin >> nums[i]; } pair<int, int> result = findPairWithSum(nums, n); if (result.first != -1) { cout << result.first << " " << result.second << endl; } else { cout << "No Answer" << endl; } return 0; } ``` 代码解释： 1. unordered_set<int> seen: 用于存储已经遍历过的数字。 2. pair<int, int> result: 用于存储最终找到的两个数。 3. int minDiff: 用于记录当前找到的最小差值。 4. for (int num : nums): 遍历数组中的每个数字。 5. int complement = n - num: 计算当前数字与目标值n的差值。 6. if (seen.find(complement) != seen.end()): 检查差值是否已经存在于哈希表中。 7. int currentDiff = abs(num - complement): 计算当前两个数的差值。 8. if (currentDiff < minDiff): 如果当前差值小于最小差值，则更新结果和最小差值。 9. seen.insert(num): 将当前数字插入哈希表中。 需要注意的逻辑点： 1. 确保输入的数字都是正整数且小于1000000。 2. 如果有多组数据满足条件，输出差值最小的一组。 3. 如果找不到满足条件的两个数，输出“No Answer”。 ######[AI写代码神器 | 568点数解答 | 2025-02-12 08:50:33]