매일 하나의 알고리즘 문제 (2): 주어진 배열 Arr 와 하나의 정수 am, 어느 두 위치의 수 를 되 돌려 am 을 추가 할 수 있 습 니까?

배열 Arr 와 정수 am 을 지정 합 니 다. 어느 두 위치 로 돌아 가면 am 을 추가 할 수 있 습 니까?
예 를 들 어 arr = {2, 7, 11, 15}, target = 9 는 {0, 1} 으로 돌아 갑 니 다. arr [0] + arr [1] = 2 + 7 = 9 는 각 배열 에 한 조 의 답 만 있다 고 가정 할 수 있 습 니 다.
대략 절 차 는 이렇다.
우선, 배열 을 정의 합 니 다.배열 의 위 치 를 기록 하 다.배열 을 정렬 하고 정렬 하 는 과정 에서 값 을 교환 하면 위 치 를 저장 하 는 배열 도 이에 따라 교환 합 니 다.
우 리 는 두 변 수 를 정의 할 수 있다.배열 의 시작 위 치 를 가리 키 며 배열 의 끝 위 치 를 가리킨다.
시작 위치 와 끝 위치 가 am 보다 크 면 끝 위치 --.
시작 위치 와 끝 위치 에 작은 am 을 더 하면 시작 위치 +.
같 으 면 배열 내 원래 위치 로 돌아 갑 니 다.
자세 한 코드 는 다음 과 같 습 니 다.

#include 
#include 
using namespace std;

//    ，               
void swap(vector &nums, vector &help,int m, int n)
{
	int tmp = nums[m];
	nums[m] = nums[n];
	nums[n] = tmp;
	
	tmp = help[m];
	help[m] = help[n];
	help[n] = tmp;
}

//     
void maxHeap(vector &nums, int start, int end, vector &help)
{
	int fNode = start;
	int sNode = 2*start+1;

	while (sNode <= end)
	{
		if (sNode+1 <= end && nums[sNode] < nums[sNode+1])
			sNode++;
		if (nums[fNode] > nums[sNode]) 
			return;
		else
		{
			swap(nums,help,sNode,fNode);
			fNode = sNode;
			sNode = fNode*2+1;
		}
	}

}

//   
void heapSort(vector &nums, vector &help)
{
	int len = nums.size();
	for(int i = len/2-1; i >= 0; i--)
	{
		maxHeap(nums, i, len-1, help);
	}
	for(int j = len-1; j >= 0; j--)
	{
		swap(nums, help, j ,0);
		maxHeap(nums,0,j-1, help);
	}
}

void twoNum(vector &nums, vector &help, vector &res, int aim)
{
	heapSort(nums,help);
	int left = 0;
	int right = nums.size()-1;
	int sum = 0;
	while (left != right)//         
	{
		sum = nums[left] + nums[right];
		if (sum > aim)
			right--;
		if (sum < aim) 
			left++;
		if (sum == aim) 
		{
			res.push_back(left);
			res.push_back(right);
			return;
		}
	}
	res.push_back(-1);
	res.push_back(-1);
}

int main(int argc, char* argv[])
{
	vector nums;
	nums.push_back(2);
	nums.push_back(11);
	nums.push_back(7);
	nums.push_back(15);
	
	vector help;
	
	vector res;

	for(int i = 0; i < 4; i++)
	{
		help.push_back(i);
	}

	twoNum(nums, help, res,26);

	for(i =0; i < 2; i++)
	{
		cout << res[i] << "\t" ;
	}
	cout << endl;

	cin.get();
	return 0;
}