【算法专题突破】双指针 - 四数之和(8)

简介: 【算法专题突破】双指针 - 四数之和(8)

1. 题目解析

题目链接:18. 四数之和 - 力扣(Leetcode)

这道题跟三数之和也是一样的,

题目很好理解,就是四个数的和等于target的情况,

且这四个数不能重复。

2. 算法原理

首先还是暴力解法:

排序 + 暴力枚举 + set去重

我们当然是用优化的解法:

1. 依次固定一个数a

2. 然后在后面的区间,找到他们的和为target - a的数

3. 而三数之和,也是固定一个数b,然后找出他们的和为target - a - b的数

但是我们也要注意,需要跳过重复元素。

3. 代码编写

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, long long target) {
        int size = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < size - 3; i++) {
            int a = nums[i];
            for(int j = i + 1; j < size - 2; j++) {
                int b = nums[j];
                int left = j + 1, right = size - 1;
                while(left < right) {
                    int sum = nums[left] + nums[right];
                    if(sum < target - a - b) left++;
                    else if(sum > target - a - b) right--;
                    else { // sum == target - a - b
                        ans.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--;
                        left++, right--;
                    }
                }
                while(j < size - 2 && nums[j] == nums[j + 1]) j++;
            }
            while(i < size - 3 && nums[i] == nums[i + 1]) i++;
        }
        return ans;
    }
};

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果感到有所收获的话可以给博主点一个哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

相关文章
|
5月前
|
算法
双指针算法
双指针算法
31 2
|
2月前
|
算法 索引 容器
双指针算法详解
本文介绍了双指针算法及其应用。双指针算法是在数组或字符串中常用的高效技术,通过维护两个指针遍历数据结构以解决特定问题。根据指针移动方向,可分为同向双指针、相向双指针和快慢指针。同向双指针如移动零和复写零问题;快慢指针如快乐数问题;相向双指针如盛水最多的容器、有效三角形数量及多数之和等问题。通过合理运用双指针技巧,可简化代码并提高效率。
60 4
双指针算法详解
|
5月前
|
机器学习/深度学习 搜索推荐 算法
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
【再识C进阶2(下)】详细介绍指针的进阶——利用冒泡排序算法模拟实现qsort函数,以及一下习题和指针笔试题
|
1月前
|
算法 C++
【算法】双指针+二分(C/C++
【算法】双指针+二分(C/C++
|
3月前
|
算法 容器
【算法】双指针
【算法】双指针
|
3月前
|
算法 C++ 容器
【C++算法】双指针
【C++算法】双指针
|
6月前
|
算法
【优选算法】——双指针——15. 三数之和
【优选算法】——双指针——15. 三数之和
【优选算法】——双指针——15. 三数之和
|
6月前
|
存储 人工智能 算法
c++算法学习笔记 (9) 双指针
c++算法学习笔记 (9) 双指针
|
6月前
|
算法
[优选算法]——双指针——Leetcode——1089. 复写零
[优选算法]——双指针——Leetcode——1089. 复写零