CC150 17.12

17_12.cpp

/* CC150 17.12 */
// find all pairs of integers within an array which sum to a specified value

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> findPairs(vector<int> arr, int sum)
{
	sort(arr.begin(), arr.end());
	vector<pair<int, int>> pairs;
	if (arr.size() < 2) {
		cout << "Not enough data!" << endl;
		return pairs;
	}
	auto left = arr.begin(), right = arr.end() - 1;
	for ( ; left != arr.end() - 1; ++left) {
		for ( ; right > left; --right) {
			if (*left + *right == sum) {
				pairs.push_back(make_pair(*left, *right--));
				break;
			}
			else if (*left + *right < sum)
				break;
		}
	}
	return pairs;
}

vector<pair<int, int>> findPairs2(vector<int> arr, int sum)
{
	sort(arr.begin(), arr.end());
	vector<pair<int, int>> pairs;
	if (arr.size() < 2) {
		cout << "Not enough data!" << endl;
		return pairs;
	}
	auto left = arr.begin(), right = arr.end() - 1;
	while (left < right) {
		if (*left + *right == sum)
			pairs.push_back(make_pair(*left++, *right--));
		else if (*left + *right > sum)
			--right;
		else
			++left;
	}
	return pairs;
}

int main()
{
	int sum;
	cout << "Enter desired sum: ";
	cin >> sum;
	vector<int> arr;
	int data;
	while (cin >> data) {
		arr.push_back(data);
	}
	vector<pair<int, int>> pairs = findPairs2(arr, sum);
	for (auto p : pairs)
		cout << "(" << p.first << ", " << p.second << ")" << endl;
	return 0;
}