정렬되지 않은 목록의 어떤 숫자를 목록의 다른 3 개의 숫자의 합으로 나타낼 수 있습니까?

Question

다음 인터뷰 질문이 온라인에서 발생하여 O (N^2) 해결책이 생겼습니다.
이 문제를 해결하는 더 좋은 방법이 있는지 알고 싶습니다.

문제점 : 순서가 지정되지 않은 목록의 어떤 숫자가 목록의 다른 3 개의 숫자의 합으로 표시 될 수 있습니까?

내 O (N^2) 용액 :

1. 모두 2 쌍 요소의 합을 저장하는 해시 맵을 만든다.
   예 : hashmap.insert (a [I] + A [J]) 0 <는 = 난 J <는 = N-1 해시 맵 1 단계에서 만들어지면

2. 은 (
   O (N^2) 시간이 걸린다 두 쌍의 요소 (a [p], a [q])의 모든 쌍에 대해, < = p, q 인 모든 쌍의 nC2 쌍을 선택하고이 쌍이
   세 번째 요소와 합계를 포함하는지 확인하십시오. < = N-1
   해시 맵의 (a [▲] - A [P])가 포함되어있는 경우 찾기

에게

Answer 1

은 할 수 없습니다 O(N^2)보다 우수합니다. 그러면 컴퓨터 과학에서 O (N^2) 미만의 3 합 문제를 해결하는 가장 어려운 문제 중 하나를 해결했을 것입니다. 3-sum이 O (N^2)보다 덜 해결 될 수 있는지 여부는 여전히 열려있는 문제입니다.

3-Sum