모든 를 배열 에, 모든 을 배열 에 넣는다. 두 배열의 길이는 각각 이다. 같은 합을 만드는 인덱스 쌍도 각각 넣어야 한다.
두 배열을 오름차순으로 정렬한다. 에서는 아직 처리하지 않은 최솟값 를, 에서는 아직 처리하지 않은 최댓값 를 본다. 이면 남은 어떤 의 원소를 에 더해도 이 되지 않으므로 쪽을 전진시킨다. 이면 남은 어떤 의 원소를 에 더해도 이 되지 않으므로 쪽을 전진시킨다.
이면 와 가 연속해서 나오는 횟수를 각각 라 하자. 두 묶음에서 하나씩 고르는 가지가 모두 정답에 포함된다. 이 값을 더하고 양쪽에서 해당 묶음을 건너뛴다. 각 값과 합이 이 되는 상대 값은 하나뿐이므로, 이 과정에서 같은 인덱스 튜플을 두 번 세지 않는다.
시간 복잡도는 이고 공간 복잡도는 이다. 네 원소의 합은 32비트 부호 있는 정수 범위에 들어가지만, 개수의 곱과 정답은 최대 이므로 64비트 정수로 계산한다.
Solution written by GPT