7257 : 이분탐색 + 투포인터
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 배열에서 두 원소의 합이 정확히 $S$가 되는 서로 다른 쌍의 개수를 구하십시오.
배열을 정렬한 후 투 포인터(Two Pointer) 기법을 사용하면 $O(N \log N)$ 시간에 해결할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
배열을 정렬한 후 투 포인터(Two Pointer) 기법을 사용하면 $O(N \log N)$ 시간에 해결할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 배열의 크기 $N$과 목표 합 $S$가 주어집니다. ($2 \le N \le 100{,}000$, $|S| \le 2 \times 10^9$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
배열의 두 원소의 합이 정확히 $S$가 되는 서로 다른 인덱스 쌍의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6 9
1 2 3 4 5 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
정렬 후 좌우 포인터를 이용합니다. 합이 $S$이면 중복 원소 처리에 주의하십시오. 같은 값의 원소가 여러 개라면 그 개수의 조합 수를 계산합니다.