프로 그래 밍 의 미 2.12 - 조건 을 만족 시 키 는 두 개 또는 세 개 수 를 신속하게 찾 습 니 다.

질문:
1. 한 배열 의 두 수 를 빨리 찾 아 이 두 수의 합 이 주어진 값 과 같 도록 한다.
2. 한 배열 의 세 수 를 빨리 찾 아 이 세 수의 합 을 주어진 값 과 같 게 한다.
1. 해법: 알고리즘 복잡 도 는 O (nlogn) 이다.먼저 배열 을 빠르게 정렬 하여 정렬 한 다음 에 두 바늘 (두 색인) 법 으로 정렬 된 배열 을 거꾸로 옮 겨 다 니 게 하고 옮 겨 다 니 는 방향 이 변 하지 않 습 니 다.(두 수의 합 을 계산 하면 i = 0, j = n - 1 로 초기 화 되 고 두 수의 차 이 를 계산 하면 i = 0, j = 1 로 초기 화 됩 니 다)
이렇게 옮 겨 다 니 는 방식 이 성공 할 수 있 는 이 유 는 정렬 후 ai + aj < sum 이면 ai + ak < sum (k = i, i + 1... j) 이 고 i 이전 j 이후 의 상황 이 옮 겨 다 녔 기 때문에 i + + 만 등호 가 있 을 수 있 습 니 다.만약 에 ai + aj > sum 이 라면 ak + aj > sum (k = i, i + 1... j) 이 고 i 이전 j 이후 의 상황 은 이미 옮 겨 다 녔 기 때문에 j - 만 등호 가 있 을 수 있 습 니 다.

#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 1001
int A[MAXN];

//         O(nlogn)
int main()
{
	int n, sum, i, j;
	cin >> n >> sum;
	for (i=0; i<n; i++)
		cin >> A[i];
	//     O(nlogn)
	sort(A, A+n);
	//        
	i=0; j=n-1;
	//         （         ，  <=）
	while (i<j)
	{
		int plus = A[i]+A[j];
		if (plus == sum)
		{
			printf("(%d,%d) ",A[i],A[j]);
			i++, j--;
		}
		else if (plus < sum)
			i++;
		else
			j--;
	}
}

2. 해법: 시간 복잡 도 는 O (n ^ 2) 입 니 다.배열 이 정렬 되 어 있 으 면 해법 1 의 더 블 포인터 역법 을 이용 하여 O (n) 의 시간 내 에 두 개의 수의 합 을 찾 을 수 있 습 니 다.우 리 는 찾 은 세 개의 수 ai, aj, ak 에 ai < = aj < = ak 가 있다 고 가정 합 니 다. ai + aj + ak = sum, 즉 ai + aj = sum - ak, subsum = sum - ak 를 설정 하면 subsum 의 값 이 n 개 밖 에 없 는 것 을 쉽게 발견 할 수 있 습 니 다. ai + aj = subsum 중의 ai, aj 는 O (n) 의 시간 만 필요 하기 때문에 전체적인 시간 복잡 도 는 O (nlogn + n * n) = O (n ^ 2) 입 니 다.

#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 1001
int A[MAXN];

int main()
{
	int n, sum, i, j, k;
	cin >> n >> sum;
	for (i=0; i<n; i++)
		cin >> A[i];
	sort(A, A+n);
	for (k=0; k<n; k++)
	{
		i=0; j=k-1;
		if (k==i) i++;
		if (k==j) j--;
		int subsum = sum-A[k];
		while (i<j)
		{
			int plus = A[i]+A[j];
			if (plus == subsum)
			{
				printf("(%d,%d,%d) ",A[i],A[j],A[k]);
				i++, j--;
			}
			else if (plus < subsum)
				i++;
			else
				j--;
			if (k==i) i++;
			if (k==j) j--;
		}
	}
}

각 수 를 여러 번 선택 할 수 있다 면 코드 를 조금 만 고 쳐 야 합 니 다. 구체 적 으로 다음 과 같 습 니 다.

#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 1001
int A[MAXN];

int main()
{
	int n, sum, i, j, k;
	cin >> n >> sum;
	for (i=0; i<n; i++)
		cin >> A[i];
	sort(A, A+n);
	for (k=0; k<n; k++)
	{
		i=0; j=k;
		//if (k==i) i++;
		//if (k==j) j--;
		int subsum = sum-A[k];
		while (i<=j)
		{
			int plus = A[i]+A[j];
			if (plus == subsum)
			{
				printf("(%d,%d,%d) ",A[i],A[j],A[k]);
				i++, j--;
			}
			else if (plus < subsum)
				i++;
			else
				j--;
			//if (k==i) i++;
			//if (k==j) j--;
		}
	}
}