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

个人主页:在线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;
    }
};

5. 夹带私货

若你能看到看到这篇文章且能看到这,则说明你我有缘留个关注吧,后面还会接着计算机408、底层原理、开源项目、以及数据、后端研发相关、实习、笔试/面试、秋招/春招、各种竞赛相关、简历相关、考研、学术相关……,祝你我变得更强


好的,到此为止啦,祝您变得更强
在这里插入图片描述

在这里插入图片描述

道阻且长 行则将至
个人主页:在线OJ的阿川大佬的支持和鼓励,将是我成长路上最大的动力 在这里插入图片描述

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部