BOJ 3273 ) 두 수의 합 (C++)

https://www.acmicpc.net/problem/3273

만만하게 봤는데 생각보다 오래 걸렸다.N이 10^6이기 때문에 무작정 이중 for문을 돌려버리면 시간초과가 난다. ai + aj = x (1 ≤ i < j ≤ n) 를 만족하는 쌍의 개수를 구해야 하는데 aj = x - ai를 만족하는 ai의 개수만 체크해주면 되기 때문에 O(N)만에 해결이 가능하다. ai와 aj는 1000000보다 작거나 같은 자연수이기 때문에 x - ai 가 범위를 벗어나지 않는지도 체크해 주어야 한다는걸 놓치는 바람에 헤맸다. 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin>>n;
    vector<int> v = vector<int>(n);
    vector<int> v1 = vector<int>(1000002);
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    cin>>k;

    int cnt = 0, aj = 0;
    for(int i=0; i<n;i++)
    {
        aj = k-v[i]; 
        if (aj <= 0 || 1000000 < aj) continue;
        cnt += v1[aj];
        v1[v[i]]++;
    }

    cout<<cnt;
    return 0;
}