이 주어 합계 값 N

Question

3의 그룹 번호의 숫자의 배열을 모두 찾을 수 있습니다 값 N (이 예에서는 11). 여기에 3 개 그룹의 가능한 숫자는 다음과 같습니다.

{1,2,8}, {1,4,6}, {0,2,9} 

내가 생각할 수있는 첫 번째 해결책은 O (n^3)입니다. 나중에 접근 방식을 조금 (n^2 log n) 향상시킬 수 있습니다.

1. Sort the array. 
2. Select any two number and perform binary search for the third element. 

다른 접근 방법으로 더 향상시킬 수 있습니까?

Answer 1

O(n^2)에서 확실히 확인할 수 있습니다. 배열의 각 i에 대해 다른 두 값의 합이 N-i 인 지 테스트합니다.

정렬 된 배열의 두 값이 k의 합계를 한 번에 스윕하여 테스트하는지 여부를 O(n)에서 테스트 할 수 있습니다. 두 요소의 합이 너무 큰 경우 "오른쪽에서 왼쪽으로"색인을 줄여서 작게 만듭니다. 합계가 너무 작 으면 "왼쪽에서 오른쪽으로"색인을 증가시켜 더 크게 만듭니다. 작업 할 수있는 쌍이있는 경우 해당 쌍을 찾을 수 있으며 한쪽 끝이나 다른 쪽 끝에서 달리기 전에 최대 2*n 번 반복 수행 할 수 있습니다. i으로 사용중인 값을 무시하는 코드가 필요할 수 있으며 규칙이 무엇인지에 따라 다릅니다.

대신 N에서 작동하는 일종의 동적 프로그래밍을 사용할 수 있으며, 아마도 O(n*N) 정도의 시간이 될 것입니다. 현실적으로 나는 그 것이 더 좋다고 생각하지 않습니다 : 모든 숫자가 음수가 아닌 것처럼 보입니다. 따라서 n이 N보다 훨씬 크면 시작하기 전에 배열에서 큰 값을 던질 수 있고 그 이상으로 중복을 던질 수 있습니다 각 값의 사본 3 개 (또는 i의 세 번째 사본을 버리기 전에 3*i == N을 확인하는 한 2 부). 이 단계 후에 n은 O(N)입니다.