온라인 평가 C++ 풀이 프롬프트

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

vector<vector<int>> f(vector<int>& a,int t)
{
    unordered_map<int,vector<int>> m;
    vector<vector<int>> r;

    for(int i=0;i<a.size();i++)
    {
        m[a[i]].push_back(i);
    }

    for(int i=0;i<a.size();i++)
    {
        auto it=m.find(t-a[i]);

        if(it==m.end())
        {
            continue;
        }

        auto& v=it->second;
        auto p=lower_bound(v.begin(),v.end(),i+1);

        for(;p!=v.end();p++)
        {
            r.push_back({i,*p});
        }
    }

    return r;
}

각 인덱스 i를 기준으로 i보다 큰 보완값의 인덱스를 찾아 결과에 추가합니다. 인덱스를 앞에서부터 처리하므로 결과는 i 기준 오름차순이며, 시간 복잡도는 O(n log n+k), 공간 복잡도는 O(n+k)입니다. 여기서 k는 결과 쌍의 개수입니다.

예시의 올바른 결과는 [[0,1],[4,5]]입니다.