在数组中找出两个数a、b，使得a加b等于给定的c

- 日理万妓 2022-08-04 00:57 208阅读 0赞

题目：有一个整数数组array，给定整数sum，从这两个数中选取两个数a、b，使得a+b = sum。

《编程之美2.12 》

# 一、满足条件的两个数 #

找出两个数a、b，使得a + b = sum；等价于：从数组中找一个数b使得 b = sum - a;

## 方法一 ##

//方法一：穷举法。查找任意两个数，看其之和是否为给定数
    //该方法时间复杂度为O(n^2)

## 方法二 ##

//方法二：对数组排序，然后对数组中每个数进行二分查找
    //时间复杂度O(nlogn),找出所有的符合要求点对
    int binary_search1(vector<int>& vec, int first, int last, int value, int pos) {
    	if (first > last)
    		return -1;
    	int mid = (first + last) / 2;
    	
    	//当在数组中找到了一个value而且该value不是vec[i]时才是符合要求的
    	//例如数组{1,2,3,4}中sum为2的是不存在的，也就是(1,1)不符合要求
    	if (vec[mid] == value && mid != pos)
    		return mid;
    	else if (value < vec[mid])
    		binary_search1(vec, first, mid - 1, value, pos);
    	else
    		binary_search1(vec, mid + 1, last, value, pos);
    	return -1;
    }
    
    int binary_search2(vector<int>& vec, int value, int pos) {
    	int length = vec.size();
    	int first = 0, last = length - 1, mid;
    	while (first < last) {
    		mid = (first + last) / 2;
    		if (vec[mid] == value && mid != pos)
    			return mid;
    		else if (vec[mid] < value)
    			first = mid + 1;
    		else
    			last = mid - 1;
    	}
    	return -1;
    }
    void FindTwoElements2(vector<int> &vec, int sum) {
    	sort(vec.begin(), vec.end());
    	int value;
    	bool found = false;
    	for (int i = 0; i < vec.size(); ++i) {
    		value = sum - vec[i];
    		int found_pos = -1;
    		/*if ((found_pos = binary_search1(vec, 0, vec.size(), value, i)) != -1)
    		cout << "found: " << vec[found_pos] << " " << vec[i] << endl;*/
    		if ((found_pos = binary_search2(vec, value, i)) != -1) {
    			cout << "found: " << vec[found_pos] << " " << vec[i] << endl;
    			found = true;
    		}
    	}
    	if (!found)
    		cout << "not found" << endl;
    }

## 方法三 ##

//方法三：对数组排序，然后两个指针分别从数组首尾进行遍历
    //该方法找到一对符合要求的就返回
    //对数组排序时间为O(nlogn),但是两个指针遍历仅需要O(n)
    void FindTwoElements3(vector<int> &vec, int sum) {
    	sort(vec.begin(), vec.end());
    	int begin = 0, end = vec.size() - 1;
    	while (begin < end) {
    		if (vec[begin] + vec[end] == sum) {
    			cout << "found: " << vec[begin] << " " << vec[end] << endl;
    			return;
    		}
    		else if (vec[begin] + vec[end] > sum)
    			--end;
    		else
    			++begin;
    	}
    	cout << "not found" << endl;
    	return;
    }

## 方法四 ##

将数组的元素全部哈希，这个过程需要O(n)的时间和空间，但是查找一个数b=sum - a仅需要时间O(1)；那么，对于数组中的每个元素，查找符合要求的b，需要时间总共为O(n）。

# 二、满足条件的三个数 #

找出两个数a、b、c，使得a + b + c = sum

## 方法一 ##

将三个数的情况转换为两个数的情况

//遍历每个数组元素，对每个vec[i]调用上面的求两个数之和
    //的方法：FindTwoElements2(vec, sum - vec[i]);
    //该方法允许一个元素被找多次，例如main函数中：1,1,2符合sum等于4的要求
    void FindThreeElements(vector<int>& vec, int sum) {
    	for (int i = 0; i < vec.size() / 2; ++i) {
    		cout << vec[i] << " ";
    		FindTwoElements2(vec, sum - vec[i]);
    	}
    }

//不允许一个元素找多次，找到一组符合要求的就返回
    void FindThreeElements2(vector<int>& vec, int sum) {
    	int subsum;
    	bool found = false;
    	//如果数组无序先对数组排序
    	//sort(vec.begin(), vec.end()); 
    	sort(vec.begin(), vec.end());
    	for (int k = 0; k < vec.size(); ++k) {
    		subsum = sum - vec[k];
    		int begin = 0, end = vec.size() - 1;
    		while (begin < end) {
    			if (begin == k)  ++begin;
    			if (end == k)  --end;
    			if (vec[begin] + vec[end] == subsum) {
    				cout << vec[k] << " " << vec[begin] << " " << vec[end] << endl;
    				++begin;
    				--end;
    				return;
    			}
    			else if (vec[begin] + vec[end] < subsum)
    				++begin;
    			else
    				--end;
    		}
    	}
    	cout << "not found" << endl;
    }

## 方法二 ##

先排序，然后前后指针

//上面方法二是将三个数的转化为两个数的情况，这里直接遍历
    //如果数据没有排序要先排序！！！
    //先排序，然后前后指针，时间O(n^2)
    vector<vector<int> > FindThreeElements3(vector<int>& vec, int sum) {
    	vector<vector<int> > result;
    	if (vec.size() < 3) //元素个数小于三个直接返回空
    		return result;
    
    	sort(vec.begin(), vec.end());
    	for (int a = 0; a < vec.size() - 2; ++a) {
    		int b = a + 1, c = vec.size() - 1;
    		while (b < c) {
    			if (vec[a] + vec[b] + vec[c] < sum)
    				++b;
    			else if (vec[a] + vec[b] + vec[c] > sum)
    				--c;
    			else {
    				vector<int> temp;
    				temp.push_back(vec[a]);
    				temp.push_back(vec[b]);
    				temp.push_back(vec[c]);
    				result.push_back(temp);
    				++b;
    				--c;
    			}
    		}
    	}
    
    	//去除结果集中重复的内容
    	sort(result.begin(), result.end());
    	result.erase(unique(result.begin(), result.end()), result.end());
    	return result;
    }

# 三、满足条件的三个数（离sum最近的三数之和） #

上面的几个算法，如果数组中没有满足条件的两个数或三个数的话，算法就返回空；这里的题目是要求返回三数之和sum，使得这个和sum最接近给定的整数target。

//上面的拓展中，一定存在a+b+c等于sum，这里要求的是最接近的
    //函数返回最接近target的sum值
    //如果数据没有排序要先排序！！！
    //先排序，然后前后指针，时间O(n^2)
    int FindThreeClosest(vector<int>& vec, int target) {
    	int result;  //记录最终的sum，即最接近target的三数和
    	int min_gap = INT_MAX;  //记录target与sum的最小差值
    	vector<int> result_elements(3, 0); //记录最终的三个数
    
    	sort(vec.begin(), vec.end());
    	for (int a = 0; a < vec.size() - 2; ++a) {
    		int b = a + 1, c = vec.size() - 1;
    		while (b < c) {
    			int sum = vec[a] + vec[b] + vec[c];
    			int gap = abs(sum - target);
    			if (gap < min_gap) {
    				result = sum;
    				//更新三个数
    				result_elements[0] = vec[a];
    				result_elements[1] = vec[b];
    				result_elements[2] = vec[c];
    				min_gap = gap;
    			}
    			if (sum < target)  ++b;
    			else   --c;
    		}
    	}
    	cout << result_elements[0] << " " << result_elements[1] << " " 
    		<< result_elements[2] << " sum: ";
    	return result;
    }

# 四、寻找满足的四个数 #

从数组中找a、b、c、d，使得a + b + c + d 等于给定的target。

## 方法一 两个指针 ##

//有多个时符合要求的情况，打印所有的情况
    //方法一：
    //先排序，然后前后指针，时间O(n^3)
    void PrintFourElementsResult(vector<vector<int> >& result);
    vector<vector<int> > FindFourElements(vector<int>& vec, int target) {
    	vector<vector<int> > result;
    	if (vec.size() < 4) //元素个数小于四个直接返回空
    		return result;
    
    	sort(vec.begin(), vec.end());
    
    	for (int a = 0; a < vec.size() - 3; ++a) {
    		for (int b = a + 1; b < vec.size() - 2; ++b) {
    			int c = b + 1;
    			int d = vec.size() - 1;
    			while (c < d) {
    				if (vec[a] + vec[b] + vec[c] + vec[d] < target)
    					++c;
    				else if (vec[a] + vec[b] + vec[c] + vec[d] > target)
    					--d;
    				else {
    					vector<int> temp;
    					temp.push_back(vec[a]);
    					temp.push_back(vec[b]);
    					temp.push_back(vec[c]);
    					temp.push_back(vec[d]);
    					result.push_back(temp);
    					++c;
    					--d;
    				}
    			}
    		}
    	}
    	//去除结果集合中重复的
    	sort(result.begin(), result.end());
    	result.erase(unique(result.begin(), result.end()), result.end());
    	return result;
    }

## 方法二 map ##

//有多个时情况时，打印所有的情况
    //方法二：使用map
    //先排序，然后将两个数的和缓存
    //时间复杂度平均O(n^ 2),最坏O(n ^ 4);空间O(n^2)
    vector<vector<int> > FindFourElements2(vector<int>& vec, int target) {
    	vector<vector<int> > result;
    	if (vec.size() < 4)
    		return result;
    	sort(vec.begin(), vec.end());
    
    	//map用于缓存两个数的和，键：两数的和；值：这两个数的下标
    	map<int, vector<pair<int, int> > > cache;
    	for (int a = 0; a < vec.size(); ++a) {
    		for (int b = a + 1; b < vec.size(); ++b)
    			cache[vec[a] + vec[b]].push_back(make_pair(a, b));
    	}
    
    	for (int c = 0; c < vec.size(); ++c) {
    		for (int d = c + 1; d < vec.size(); ++d) {
    			int key = target - vec[c] - vec[d];
    
    			//如果当前的两个数之和与cache中两数之和的和不符合要求，继续
    			if (cache.find(key) == cache.end())
    				continue;
    
    			vector<pair<int, int> > temp_vec = cache[key];
    			for (int k = 0; k < temp_vec.size(); ++k) {
    				if (c <= temp_vec[k].second)
    					continue;  //有重叠
    				vector<int> temp;
    				temp.push_back(vec[temp_vec[k].first]);
    				temp.push_back(vec[temp_vec[k].second]);
    				temp.push_back(vec[c]);
    				temp.push_back(vec[d]);
    				result.push_back(temp);
    			}
    		}
    	}
    	
    	//去除结果集中重复的
    	sort(result.begin(), result.end());
    	result.erase(unique(result.begin(), result.end()), result.end());
    	return result;
    }

## 方法三 multimap ##

//有多个时，打印所有的情况
    //方法三：使用multimap
    //先排序，然后将两个数的和缓存
    //时间复杂度平均O(n^ 2);空间O(n^2)
    //该函数用于输出四个数时的结果
    vector<vector<int> > FindFourElements3(vector<int>& vec, int target) {
    	vector<vector<int> > result;
    	if (vec.size() < 4)
    		return result;
    	sort(vec.begin(), vec.end());
    
    	//multimap存放两个数和，以及两个数的下标
    	multimap<int, pair<int, int> > cache;
    	for (int a = 0; a < vec.size() - 1; ++a) {
    		for (int b = a + 1; b < vec.size(); ++b)
    			cache.insert(make_pair(vec[a] + vec[b], make_pair(a, b)));
    	}
    
    	//取出cache中两个和，如果这两个和的和等于target，而且组成这两对和
    	//的四个数互不相同（它们的下标不同），则这四个数就是符合的一个解
    	multimap<int, pair<int, int> >::iterator iter;
    	for (iter = cache.begin(); iter != cache.end(); ++iter) {
    		int subsum = target - iter->first; 
    		typedef multimap<int, pair<int,int> >::iterator mul_iter;
    
    		//从cache中找到符合subsum + iter->first等于target的四个数
    		pair<mul_iter, mul_iter> range = cache.equal_range(subsum);
    
    		mul_iter iter_in;
    		for (iter_in = range.first; iter_in != range.second; ++iter_in) {
    			int a = iter->second.first;
    			int b = iter->second.second;
    			int c = iter_in->second.first;
    			int d = iter_in->second.second;
    			if (a != c && a != d && b != c && b != d) {
    				vector<int> temp;
    				temp.push_back(vec[a]);
    				temp.push_back(vec[b]);
    				temp.push_back(vec[c]);
    				temp.push_back(vec[d]);
    				//注意这里先将符合要求的四个数排序，以便下边删除重复的
    				sort(temp.begin(), temp.end());
    				result.push_back(temp);
    			}
    		}
    	}
    	sort(result.begin(), result.end());
    	result.erase(unique(result.begin(), result.end()), result.end());
    	return result;
    }

# 测试函数 #

//该函数用于输出满足条件的四个数的结果集合
    void PrintFourElementsResult(vector<vector<int> >& result) {
    	if (result.size() == 0)
    		cout << "not found" << endl;
    	vector<vector<int> >::iterator iter = result.begin();
    	while (iter != result.end()) {
    		vector<int>::iterator iter_in = (*iter).begin();
    		while (iter_in != (*iter).end())
    			cout << *iter_in++ << " ";
    		cout << endl;
    		++iter;
    	}
    }
    
    int main() {
    	int a[] = {1,2,3,4,5,6,7,8,9,10,11};
    	vector<int> vec(a, a + sizeof(a) / sizeof(int));
    	int value;
    	while (cin >> value) {
    		//FindTwoElements2(vec, value);
    		//FindTwoElements3(vec, value);
    		//FindThreeElements2(vec, value);
    
    		//vector<vector<int> > result = FindThreeElements3(vec, value);
    		//PrintFourElementsResult(result);
    
    		//int result = FindThreeClosest(vec, value);
    		//cout << result << endl;
    
    		//vector<vector<int> > result1 = FindFourElements(vec, value);
    		//PrintFourElementsResult(result1);
    		//cout << endl;
    
    		vector<vector<int> > result = FindFourElements2(vec, value);
    		PrintFourElementsResult(result);
    		cout << endl;
    
    		vector<vector<int> > result2 = FindFourElements3(vec, value);
    		PrintFourElementsResult(result2);
    		cout << endl;
    	}
    }

# 总结 #

**上面的几种问题中，无论是求满足的条件的两个、三个还是四个数时，都用到了前后两个指针移动的方法。**

**对于此方法，可以推广的求满足条件的k个数（k-sum）：对数组先排序，然后做k -2层循环，在最内层循环左右指针，时间复杂度为O(max\{nlogn, n^(k - 1)\})。**

上面完整源码参考github： [https://github.com/liyangddd/algorithms/blob/master/beauty\_of\_programming\_Ch2.cpp\#L211][https_github.com_liyangddd_algorithms_blob_master_beauty_of_programming_Ch2.cpp_L211] （搜索“2.12”）

[https_github.com_liyangddd_algorithms_blob_master_beauty_of_programming_Ch2.cpp_L211]: https://github.com/liyangddd/algorithms/blob/master/beauty_of_programming_Ch2.cpp#L211