思路比较简单，将两个指针分别指向数组的前后两端，如果和大于 sum，就向左移动右侧指针，如果和小于 sum，就向右移动左侧指针。因为一开始就是在数组两边，两个指针比较分散，所以在第一次和等于 sum 的时候，由基本不等式可以得出，答案一定是乘积最小的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> result;
if(array.size()<2) return result;
int i=0,j=array.size()-1;
while(i<j){
int s=array[i]+array[j];
if(s>sum) j--;
else if(s<sum) i++;
else{
result.push_back(array[i]);
result.push_back(array[j]);
return result;
}
}
return result;
}
};
|