Sum of Two Values

想法 – 1

用hash map, 也就是python的dict來記錄下位置，並在每一個迴圈都比較現在 x-i的值有沒有在li裡，有的話就輸出dicta對應的位置。

n,x = map(int,input().split())
li = list(map(int,input().split()))

d = dict((v,k+1) for k,v in enumerate(li))
for i in range(len(li)):
    s = x - li[i]
    if s in li and d[s] != i+1:# 因為題目說一定要兩個數字sum
        print(i+1,d[s])
        break
else:
    print("IMPOSSIBLE")

但是這種寫法會跑太多迴圈，超時。（

因為 li 是個 list，in 判斷會是 O(n) 的操作。整體會退化成 O(n²)！）即使改成if s in d 也還是會超時！！

改Ｃ＋＋

並且在同個迴圈中加入map，避免「重複的數字」只保留到最後一個出現的位置，也減少迴圈運行的時間

#include <bits/stdc++.h>
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int i;
typedef long long ll;

int main(){
    io;

    int n,x,a,s;
    cin >> n>>x;
    map<int,int> d;
    vector<int> li;

    for (i=0;i<n;i++){
        cin >> a;
        s = x-a;
        if (d.count(s) and d[s]!=i+1){
            cout << i+1 <<" " << d[s];
            return 0;
        }
        if (!d.count(s)) d[a]=i+1;
    }
    cout << "IMPOSSIBLE\n";
}