본문 바로가기

Programming Problems/Arrays

N개의 정수 배열에서 두개의 합이 target 이하인 모든 조합 찾기

// sort 후에 head tail 기법을 사용한다.


vector<pair<int,int>> findtwo(vector<int> & data, int target){

// sort

sort(data.begin(),data.end());

// go through array

int tail = 0;

vector<pair<int,int>> ret;

for(int i = 0 ; i < data.size() ; i++){

while(data[i]-data[tail]< target){

ret.push_back(pair<int,int>(data[tail],data[i]));

tail++;

}

}

return ret;

}


time complexity : O(NlogN), bucket sort 같은걸 사용 가능하면 O(N)..