題意#
題目給定一個長度為 \( n \) 的整數陣列，以及目標總和 \( x \)。
需要在陣列中找出「三個不同位置」的數字，使得相加總和等於 \( x \)。
若找到，輸出這三個數字在原始陣列中的索引位置；若無解，則輸出 IMPOSSIBLE。
思路#
此為經典的「3Sum」問題。
若使用三重迴圈窮舉，時間複雜度為 \(\mathcal{O}(N^3)\)，會導致 TLE。
為了降低複雜度，可結合「排序」與「雙指標（Two Pointers）」。
首先，將數字與原始索引打包（例如使用 pair），並依照數字從小到大排序以保留輸出所需的原始位置。
尋找三個數字的策略為：「固定一個數字，尋找另外兩個」。
利用迴圈遍歷陣列，固定數字 v[i]。
接著目標轉化為：在它「右側」的數字中，尋找兩個相加等於 x - v[i] 的數字。
這將問題轉換為雙指標應用場景：
設定左指標 l 於 i 的下一個位置，右指標 r 於陣列的最末端，向中間靠攏：
- 若總和
sum小於目標，代表需較大的數，將左指標l往右移。 - 若總和
sum大於目標，代表需較小的數，將右指標r往左移。 - 若恰好
sum == x，即找到配對，提取原始索引並結束迴圈。
整體時間複雜度為 \(\mathcal{O}(N^2)\)。
程式碼#
#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();
int n, x; cin >> n >> x;
vector<PII> v(n);
for (auto &i : v) cin >> i.fi, i.se = &i-v.data()+1;
sort(all(v));
int a, b, c; a = -1;
for (int i = 0; i < n; i++) {
for (int l = i+1, r = n-1; l < r;) {
int sum = v[l].fi + v[r].fi + v[i].fi;
if (sum < x) l++;
else if (sum > x) r--;
else {
a = v[i].se, b = v[l].se, c = v[r].se;
break;
}
}
}
if (~a) cout << a << ' ' << b << ' ' << c;
else cout << "IMPOSSIBLE";
}
