当前位置：首页 > news >正文

【OJ刷题】双指针问题6

news 2024/9/25 23:16:13

这里是阿川的博客，祝您变得更强

✨ 个人主页：在线OJ的阿川
💖文章专栏：OJ刷题入门到进阶
🌏代码仓库：

写在开头

现在您看到的是我的结论或想法，但在这背后凝结了大量的思考、经验和讨论

在这里插入图片描述

1. 题目介绍

难度：中
题目练习：四数之和
题目信息：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案。
举个例子： 具体如图1所示

图1 举个例子

2. 题目拆解

本质上：观察规律，双指针遍历判断
特点是：在组合搭配中有一定规律
解决方法：双指针算法，如图2所示

图2 双指针

3. 具体详情

1. 先进行排序
2. 依次固定一个数并确保固定时，若是重复固定值时跳过
3. 在固定数后面的区间内利用"三数之和"找到三个数，然后再固定一个数，在固定的这个数后面的区间内，利用"双指针"找到两个数，使这两个数的和等于目标值减去两个固定值并遍历完整个数组，并确保当双指针和固定值是重复值时跳过
4. 最后返回数组

4. 具体代码

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, long long target){// 进行排序sort(nums.begin(), nums.end());vector<vector<int>> cur;int n = nums.size();// 第1层固定值for(int i = 0; i < n; ){// 第2层固定值for(int j = i + 1; j < n; ){int left = j + 1, right = n - 1;long long aim = target - nums[i] - nums[j];// 双指针算法具体实现while(left < right){int sum = nums[left] + nums[right];// 三种情况if(sum > aim) right--;else if(sum < aim) left++;else{cur.push_back({nums[i], nums[j], nums[left++], nums[right--]});// 去重while(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}j++;// 第2层固定值去重while(j < n && nums[j] == nums[j - 1]) j++;}i++;// 第1层固定值去重while(i < n && nums[i] == nums[i - 1]) i++;}return cur;}
};