输入 n ( ≤ 1 0 5 ) n(\le 10^5) n(≤105),找出其中2个数之和等于 m m m

解法一：暴力枚举 O ( n 2 ) O(n^2) O(n2)

解法二：二分搜索 O ( n l o g n ) O(nlogn) O(nlogn)

先对数组排序，然后对数组中的每个arr[i]，二分查找m-arr[i]

解法三：双指针 O ( n l o g n ) O(nlogn) O(nlogn)

先对数组排序，然后使用两个指针， i = 0 , j = n − 1 i=0,j=n-1 i=0,j=n−1,判断arr[i]+arr[j]与m的大小。
当 a r r [ i ] + a r r [ j ] > m arr[i]+arr[j]>m arr[i]+arr[j]>m时，j–
当 a r r [ i ] + a r r [ j ] &lt; m arr[i]+arr[j]&lt;m arr[i]+arr[j]<m时，i++
查找时的时间复杂度是线性的，但是总的时间复杂度还是 O ( n l o g n ) O(nlogn) O(nlogn)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int arr[maxn];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	sort(arr,arr+n);
	int i,j=n-1;
	while(arr[i] + arr[j] != m){
		if(arr[i]+arr[j]>m) j--; 
		else if(arr[i]+arr[j]<m) i++;
	} 
	cout<<arr[i]<<" "<<arr[j]<<endl;
	return 0;
}