題意#
題目給定一個長度為 \( n \) 的整數陣列，以及目標總和 \( x \)。
需要在陣列中找出兩個「不同位置」的數字，使得相加總和等於 \( x \)。
若找到，則輸出它們的位置（1-indexed）；若無解，則輸出 IMPOSSIBLE。
思路#
本題即為經典的「Two Sum」問題。
為了在「線性掃描次數內」找齊配對，可以搭配使用 Hash Map（如 C++ 中的 std::map）。
當掃描到數字 \( t \) 時，我們目標尋找對應的數字為 \( x - t \)。
每次讀取數字時，先在 Map 中查詢「先前是否已出現過 \( x - t \)」。
若已出現，則直接輸出 Map 中紀錄的位置以及當前數字的位置，並結束程式。
若尚未出現，則將當前數字 \( t \) 及位置登記至 Map 中，以供後續的數字查詢。
若遍歷完整個陣列依舊無法找到組合，最後輸出 IMPOSSIBLE。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
// i 為位置計算器（1-indexed）
int n, x, t, i = 1;
cin >> n >> x;
// mp 負責記錄每個出現過的數字，對應的原始索引位置
map<int, int> mp;
// 一邊讀入數字，一邊進行配對尋找
while (n--) {
cin >> t;
// 如果發現過去有人登記過我們所需要的配對數字 (x-t)
if (mp[x-t])
// 提取出當時登記的位置，並印出當下數字的位置 i，結束程式
return cout << mp[x-t] << ' ' << i, 0;
// 若無配對數字，把目前的數字 t 跟位置 i 登記到 map 裡面
else
mp[t] = i++;
}
// 遍歷完整個陣列依舊沒有配對成功的話
cout << "IMPOSSIBLE";
}
