南京疫情最新数据_潍坊专业捞泵电话_怎么看百度关键词的搜索量_员工培训

时间:2025/7/15 0:58:34来源：https://blog.csdn.net/hlyd520/article/details/142707149 浏览次数:0次

文章目录

- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
- 图解

题目链接：

18.四数之和

题目描述：

1d9e7dd9cd71e7b5bc1afe93fc294f66

解法

解法一：排序+暴力枚举+利用set去重

解法二：排序+双指针

从左往右依次固定一个数a
在a后面的区间里，利用“三数之和”找到三个数，使这三个数的和等于target-a即可
在上面一步的“三数之和”里面，我们先固定一个b，在b后面的区间里面，利用“双指针”找到两个数，使这两个数的和等于target-a-b即可。

处理细节：

不重

双指针要跳过相同元素
b要跳过相同元素
a要跳过相同元素

不漏

双指针遇到合适的数继续往后走

C++ 算法代码：

class Solution 
{public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;// 1. 排序sort(nums.begin(), nums.end());// 2. 利用双指针解决问题int n = nums.size();for(int i = 0; i < n; ) // 固定数 a{// 利用 三数之和for(int j = i + 1; j < n; ) // 固定数 b{// 双指针int left = j + 1, right = n - 1;long long aim = (long long)target - nums[i] - nums[j];//aim = target - a - bwhile(left < right){int sum = nums[left] + nums[right];if(sum < aim) {left++;}else if(sum > aim) {right--;}else{ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});//ret数组存放最终结果// 去重一while(left < right && nums[left] == nums[left - 1]) { left++;}while(left < right && nums[right] == nums[right + 1]) {right--;}}}// 去重二j++;while(j < n && nums[j] == nums[j - 1]) {j++;}}// 去重三i++;while(i < n && nums[i] == nums[i - 1]) {i++;}}return ret;}
};