N 개의 수 를 가 진 배열 은 이 배열 의 두 개의 수 를 찾 아 이 두 개의 수 를 0 에 가장 가 깝 게 한다.

N 개의 수가 있 는 배열 은 순서 가 없다.지금 문 제 는 배열 에서 두 개의 수 를 찾 아 이 두 개의 수 를 가능 한 한 0 에 가 깝 게 하 는 것 이다.
생각 나 는 방법 은 모든 수 대 < xi, xj > 의 조합 을 시도 한 후에 그 중의 절대 치 와 가장 작은 수 대 를 찾 으 면 된다.하지만 이렇게 하 는 시간 복잡 도 는 O (N ^ 2) 인 데 좀 더 빠 른 방법 이 없 을까요?
여기에 O (NLogN) 시간의 복잡 도 알고리즘 을 제시 합 니 다.
비교적 직관 적 인 방법 이 있다.
배열 에 순 서 를 매 긴 후.만약 숫자 가 전부 양수 라면, 가장 작은 두 수의 합 을 취한 다.만약 숫자 가 전부 마이너스 라면, 가장 큰 두 숫자의 합 을 취한 다.숫자 에 플러스 와 마이너스 가 있다 면.그러면 우 리 는 모든 xi 를 매 거 한 후에 2 분 으로 배열 에서 xi 와 같은 최대 치 와 같은 - xi 보다 큰 최소 치 를 찾 아야 한다.xi 와 구성 할 수 있 는 절대 치가 가장 작은 숫자 는 틀림없이 이 두 숫자 중의 하나 일 것 이다.모든 xi 가 매 거 진 후에 우 리 는 절대 치 의 최소 치 를 찾 을 수 있다.시간 복잡 도 는 O (NLogN) 다.
비교적 간편 한 방법 도 있 지만 좀 복잡 하 다 는 것 을 증명 한다.
1. 배열 의 수 를 작은 것 에서 큰 것 으로 정렬 합 니 다.2: 두 개의 커서 를 설정 하고 하 나 는 첫 번 째 수 를 가리 키 며 다른 하 나 는 마지막 수 를 가리 키 며 다음 과 같은 조작 을 한다. 커서 에 있 는 두 개의 수 를 절대 치 를 더 해서 현재 얻 은 최소 절대 치 를 기록 하 는 것 과 비교 하고 작은 것 은 기록한다.그 다음 에 커서 의 수의 절대 치 를 비교 하고 이동 지향 숫자 가 절대적 으로 작은 커서 (왼쪽 커서 가 가리 키 는 숫자 가 절대적 으로 작 으 면 오른쪽으로 이동 합 니 다. 그렇지 않 으 면 오른쪽 커서 가 왼쪽으로 이동 합 니 다).최소 절대 치 0 이나 커서 가 만 날 때 까지 이 단 계 를 반복 합 니 다.

    ：



    ：



-2 3 4 -7 9 5



   ：



-7 -2 3 4 5 9



    ：



res = MAX_INF;



-7 -2 3 4 5 9

|           |         res = 2



-7 -2 3 4 5 9

|         |           res = 2



-7 -2 3 4 5 9

    |     |           res = 2



-7 -2 3 4 5 9

    |   |             res = 2



-7 -2 3 4 5 9

    | |               res = 1



-7 -2 3 4 5 9

    |                 res = 1

이런 알고리즘 을 제 시 했 지만 이 알고리즘 이 정확 하 다 는 것 을 어떻게 증명 합 니까?아래 의 증명 은 매우 번거롭다.
증명:
정렬 순서
x[1],x[2],......,x[i],x[i+1],......,x[j],x[j+1],......,x[n-1],x[n]
가설 최 우 해 는 < x [i], x [j] >
x[1],x[2],......,x[i],x[i+1],......,x[j],x[j+1],......,x[n-1],x[n]                              |                                   |
만약 알고리즘 이 정확 하 다 면 알고리즘 을 실행 하 는 과정 에서 커서 가 가장 좋 은 해 를 놓 치지 않 는 다 는 것 을 증명 해 야 한다.
초기 에 커서 가 < 1, n > 이 었 는데 가장 좋 은 해 를 놓 치지 않 았 습 니 다.이후 한 걸음 한 걸음 씩 커서 가 움 직 였 다.그러면 분명히 커서 가 가장 좋 은 위치 에 먼저 도착 할 것 이다.예 를 들 어 왼쪽 커서 가 x [i] 의 위치 에 가장 먼저 도착 하고 다른 커서 의 위 치 는 k > j 이다.
x[1],x[2],....,x[i],x[i+1],....,x[j],x[j+1],....x[k],....,x[n-1],x[n]                 |                                |
다음은 상황 별로 토론 한다.
(1): x[i] > 0
이러한 상황 에서 분명히 x [j] > 0, x [k] > 0, 그리고 x [i] + x [k] > x [i] + x [j] 는 오른쪽 커서 를 왼쪽으로 이동 하 는 것 이 좋 고 최 적 화 를 놓 치지 않 을 것 이다.
(2): x[i] < 0，x[j] > 0
이 경우 3 중 소 상황 으로 나 뉜 다.
2.1: x[i]+x[j] > 0
이 경우 x [i] + x [k] > 0 및 x [i] + x [j] < x [i] + x [k] (x [j] < x [k] 때문에) 오른쪽 커서 를 왼쪽으로 이동 하 는 것 이 좋 고 최 적 화 를 놓 치지 않 습 니 다.
2.2: x[i]+x[j] < 0, x[i]+x[k] < 0
이러한 상황 에서 분명 | x [i] + x [k] | < | x [i] + x [j] |, 출시 < x [i], x [j] > 는 최 적 화 된 것 이 아니 라 가설 과 모순 되 기 때문에 최 적 화 된 상황 이 발생 하기 전에 이런 상황 은 나타 나 지 않 을 것 이다.
2.3: x[i]+x[j] < 0, x[i]+x[k] > 0
이 경우 에는 | x [i] + x [j] | < x [i] + x [k] = > - x [i] - x [j] + x [k] = > x [j] + x [k] > - 2 * x [i] = > x [k] > - x [i] = | x [i] | (x [j] < - x [i] 때 문) 가 있 습 니 다.즉, 이런 상황 에서 우 리 는 위 치 를 k 라 는 커서 로 이동 하고 위 치 를 i 라 는 커서 로 이동 하지 않 기 때문에 최 적 화 를 놓 치지 않 는 다.
(3): x[i] < 0, x[j] < 0
이런 상황 에서 도 계속 두 가지 작은 상황 으로 나 뉜 다.
3.1 x [k] < 0 이런 상황 에서 < x [i], x [j] 는 최 적 화 된 것 이 아니 라 가설 과 모순 되 기 때문에 최 적 화 된 상황 이 발생 하기 전에 이런 상황 이 나타 나 지 않 습 니 다.
3.2 x[k] > 0
이런 상황 에서 도 두 가지 작은 상황 으로 나 뉜 다.
3.2.1 x [i] + x [k] < 0 | x [i] + x [j] | < | x [i] + x [k] | = > - x [i] - x [j] < - x [i] - x [k] = > x [j] > x [k] 와 모순 된다. x 는 정렬 된 배열 이기 때문이다.그래서 이런 상황 은 최 적 화 를 만 나 기 전 까지 는 나타 나 지 않 는 다.
3.2.2 x[i]+x[k] > 0
|x[i]+x[j]| < |x[i]+x[k]| => -x[i]-x[j] < x[i]+x[k] => x[k]+x[j] > -2*x[i]=> x[k] > -2*x[i]-x[j] => x[k] > |x[i]|。즉, 이런 상황 에서 우 리 는 위 치 를 k 라 는 커서 로 이동 하고 위 치 를 i 라 는 커서 로 이동 하지 않 기 때문에 최 적 화 를 놓 치지 않 는 다.
대칭 성 으로 오른쪽 커서 가 먼저 x [j] 에 도 착 했 을 때 이런 상황 을 증명 할 수 있다.
다시 말하자면 알고리즘 과정 을 반복 하면 우리 의 커서 는 반드시 최 적 화 된 < i, j > 상태 에 도달 할 수 있 고 우리 가 사용 하 는 방법 은 최소 치 를 계속 기록 하면 우 리 는 반드시 최 적 화 를 얻 을 수 있 을 것 이다.
 
3 층 은 절대 치 에 따라 순 위 를 매 기 는 매우 간편 한 방법 을 제시 했다.곰 곰 이 생각해 보면 사실은 내 위의 방법의 또 다른 형식 이다.
예컨대

-7 -2 3 4 5 9

  3    ，    -2 3 4 5 7 9              。               ，    9 7 5 4 3 -2，                         。