AcWing 75. 和为S的两个数字
原题链接
简单
作者:
李大戮
,
2019-08-25 00:11:56
,
所有人可见
,
阅读 709
算法1
(暴力枚举) $O(n^2)$
C++ 代码
class Solution {
public:
vector<int> findNumbersWithSum(vector<int>& nums, int target) {
vector <int> a;
for(int i = 0; i < nums.size(); i++) {
for(int j = nums.size() - 1; j >=0; j--) {
if(nums[i] + nums[j] == target) {
a.push_back(nums[i]);
a.push_back(nums[j]);
return a;
}
}
}
return a;
}
};
双指针算法
class Solution {
public:
vector<int> findNumbersWithSum(vector<int>& nums, int target) {
//先对vector进行排序,然后再使用双指针算法
sort(nums.begin(),nums.end());
vector <int> a;
int i = 0, j = nums.size() - 1;
while(i < j) {
if (nums[i] + nums[j] == target) {
a.push_back(nums[i]);
a.push_back(nums[j]);
return a;
} else if (nums[i] + nums[j] < target) {
//因为已经是排好序了,所以nums[j]肯定为最大,如果sum比目标小,移动i指针
i++;
} else {
j--;
}
}
return a;
}
};