0%

CodingInterview-和为S的两个数字

思路比较简单,将两个指针分别指向数组的前后两端,如果和大于 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;
}
};