제목 설명

이것은 한 인터넷 회사의 면접 문제로 승차순으로 정렬된 수조와 하나의 숫자 n을 입력하여 수조에서 두 개의 수를 찾아 그들의 합이 그 입력 숫자 n과 꼭 같도록 요구한다.만약 숫자의 합이 n과 같으면 임의의 쌍을 출력하면 된다.

소박한 해법

두 변수 i와 j를 사용하여 두 층의 순환을 이용하여 수조를 훑어보고 데이터 [i]+데이터 [j]가 입력 숫자와 같고 i가 j와 같지 않을 때 데이터 [i]와 데이터 [j]를 출력하면 원하는 두 개의 숫자를 찾을 수 있다.다음은 이 해법의 코드입니다.

void find1(int *data,int num)
{
	assert(NULL!=data);

	int i=0;
	int j=0;
	for(i=0;i<len;i++)
		for(j=0;j<len;j++)
			{
				if((i!=j)&&((data[i]+data[j])==num))
					{
						printf(" %d + %d = %d  
",data[i],data[j],num);
						return;
					}					
			}
	printf(" not find them  
");
	return;
}

이런 해법의 시간 복잡도는 o(n^2)이고 승차수조라는 조건을 충분히 이용하지 못했다는 것을 쉽게 알 수 있다.

더욱 합리적인 해법

우리는 두 변수로 수조의 첫 번째 원소와 마지막 원소, 즉 수조의 최소값과 최대값을 찾을 수 있다.이 두 숫자의 합이 입력 숫자 n과 같으면 결과를 출력하면 된다.만약 두 숫자의 합이 n보다 작으면 오른쪽으로 작은 값을 가리키는 변수를 이동한다.만약 두 숫자의 합이 n보다 크면, 비교적 큰 값을 가리키는 변수를 왼쪽으로 이동합니다.판단이 끝나는 조건은 두 변수가 중합되는 것이다.
다음은 이 해법의 코드입니다.

void find2(int *data,int num)
{
	assert(NULL!=data);

	int i=0;
	int j=len-1;
	while(i<j)
		{
			if((data[i]+data[j])==num)
				{
					printf(" %d + %d = %d  
",data[i],data[j],num);
					return;
				}
			else if((data[i]+data[j])< num)
				{
					i++;
				}
			else
				{
					j--;
				}
		}
	printf(" not find them  
");
	return;
}

소결

두 번째 해법의 시간 복잡도는 o(n)로 첫 번째 해법보다 우수하고 제목 중의 승차수조의 조건을 충분히 이용할 수 있음을 분명히 한다.