当前位置: 首页> 游戏> 攻略 > 两数之和、三数之和-vector双指针题型

两数之和、三数之和-vector双指针题型

时间:2025/7/11 23:58:23来源:https://blog.csdn.net/user2604530353/article/details/140266206 浏览次数:0次

末尾有注意点 

167. 两数之和 II - 输入有序数组 - 力扣(LeetCode)

双指针:left、right

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int right = numbers.size() - 1;int left = 0;while(left < right){int sum = numbers[left] + numbers[right];if(sum == target)return {left+1, right +1};if(sum < target){left++;}else if(sum > target){right--;}}return {-1, -1};}
};

15. 三数之和 - 力扣(LeetCode)

转化成两数之和

class Solution {
public:vector<vector<int>> help(vector<int>& nums, int left, int right, int target, int value){vector<vector<int>>answer;while(left < right){int sum = nums[left] + nums[right];if(sum == target){vector<int> result;result.push_back(value);result.push_back(nums[left]);result.push_back(nums[right]);answer.push_back(result);while(left < right && nums[left] == nums[left+1]){left++;}left++;while(left < right && nums[right] == nums[right-1]){right--;}right--;}else if(sum < target){left++;}else{right--;}}return answer;}vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());//快排int len = nums.size();vector<vector<int>>answer;vector<vector<int>> result;for(int i = 0; i < len; i++){if(i >0 && nums[i] == nums[i-1]) {continue;}result = help(nums, i+1, len-1, -nums[i], nums[i]);answer.insert(answer.end(), result.begin(), result.end());}return answer;}
};

注意:

如果写成(nums[i] == nums[i-1] && i >0)会报错,因为先执行的nums[i-1],i-1如果= -1就会报错,i>0放前面会先执行;

关键字:两数之和、三数之和-vector双指针题型

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: