(双指针 ) 18. 四数之和 ——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了(双指针 ) 18. 四数之和 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓18. 四数之和

难度:中等

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n
  • abcd 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target
  • 你可以按 任意顺序 返回答案 。
示例 1:

输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

提示:

  • 1 < = n u m s . l e n g t h < = 200 1 <= nums.length <= 200 1<=nums.length<=200
  • − 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9 109<=nums[i]<=109
  • − 1 0 9 < = t a r g e t < = 1 0 9 -10^9 <= target <= 10^9 109<=target<=109

💡思路:排序+双指针

  • 15.三数之和 是一个思路,都是使用双指针法, 基本解法就是在三数之和 的基础上再套一层 for 循环。

🍁代码:(Java、C++)

Java

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        //极端情况返回空
        if(n < 4 || nums[0] >= 0 && nums[0] > target || nums[n - 1] < 0 && nums[n - 1] < target) return ans;
        for(int i = 0; i < n - 3; i++){
            //剪枝
            if(nums[i] >= 0 && (long)4 * nums[i] > target) break;//对nums[i]去重
            if(i > 0 && nums[i] == nums[i - 1]) continue;

            for(int j = i + 1; j < n - 2; j++){
                //二级剪枝
                if(nums[j] >= 0 && (long)3 * nums[j] + nums[i] > target) break;
                //对nums[i]去重
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1, right = n - 1;
                while(right > left){
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum < target) left++;
                    else if(sum > target) right--;
                    else{
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        if(nums[left] == nums[right]) break;//对nums[left]和nums[right]去重
                        while(right > left && nums[left + 1] == nums[left]) left++;
                        left++;
                        while(right > left && nums[right - 1] == nums[right]) right--;
                        right--;
                    }
                }
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        //极端情况返回空
        if(n < 4 || nums[0] >= 0 && nums[0] > target || nums[n - 1] < 0 && nums[n - 1] < target) return ans;
        for(int i = 0; i < n - 3; i++){
            //剪枝
            if(nums[i] >= 0 && (long)4 * nums[i] > target) break;
            //对nums[i]去重
            if(i > 0 && nums[i] == nums[i - 1]) continue;

            for(int j = i + 1; j < n - 2; j++){
                //二级剪枝
                if(nums[j] >= 0 && (long)3 * nums[j] + nums[i] > target) break;
                //对nums[i]去重
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1, right = n - 1;
                while(right > left){
                	long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum < target) left++;
                    else if(sum > target) right--;
                    else{
                        ans.push_back({nums[i], nums[j], nums[left], nums[right]});
                        if(nums[left] == nums[right]) break;//对nums[left]和nums[right]去重
                        while(right > left && nums[left + 1] == nums[left]) left++;
                        left++;
                        while(right > left && nums[right - 1] == nums[right]) right--;
                        right--;
                    }
                }
            }
        }
        return ans;
    }
};
🚀 运行结果:

(双指针 ) 18. 四数之和 ——【Leetcode每日一题】

🕔 复杂度分析:
  • 时间复杂度 O ( n 3 ) O(n^3) O(n3),其中 n 为数组的长度。排序的时间复杂度是 O ( n   l o g ⁡ n ) O(n\ log⁡n) O(n logn),枚举四元组的时间复杂度是 O ( n 3 ) O(n^3) O(n3),因此总时间复杂度为 O ( n 3 + n   l o g ⁡ n ) O(n^3 + n\ log⁡n) O(n3+n logn) = O ( n 3 ) O(n^3) O(n3)

  • 空间复杂度 O ( 1 ) O(1) O(1),忽略存储答案的空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-470366.html

注: 如有不足,欢迎指正!

到了这里,关于(双指针 ) 18. 四数之和 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【力扣每日一题】2023.7.15 四数之和

    这题和本月出过的每日一题:两数之和,三数之和类似。 不夸张的说只要把三数之和的代码拿来再套层for循环改改就可以了。 不过我这里还是简单捋一捋思路,题目给一个数组,要求返回所有长度为4,总和为 target 的子数组(不用连续)。 比较容易想到的是暴力解法,直接

    2024年02月16日
    浏览(79)
  • LeetCode 18 四数之和

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 固定两个数,然后利用双指针来进行剩下两个数的筛选 主要使用的是三数之和的思想,具体可以看我上篇博客 注意去重

    2024年02月09日
    浏览(37)
  • 18. 四数之和(力扣LeetCode)

    给你一个由 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 你

    2024年02月19日
    浏览(44)
  • 【leetcode】18. 四数之和(medium)

    给你一个由 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 你

    2024年02月13日
    浏览(43)
  • 【算法】排序+双指针——leetcode三数之和、四数之和

    三数之和 (1)排序+双指针   算法思路: 和之前的两数之和类似,我们对暴力枚举进行了一些优化,利用了 排序+双指针 的思路:   我们先排序,然后固定⼀个数 a ,接着我们就可以在这个数后面的区间内,使用之前两数之和使用的算法,快速找到两个数之和和固定的

    2024年02月13日
    浏览(53)
  • 代码随想录 Leetcode18. 四数之和

            不行了,今天做了太多n数之和要吐了,太恶心了,一堆剪枝,去重太恶心人了。最后还是照着卡哥的改

    2024年01月17日
    浏览(93)
  • 【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年04月09日
    浏览(47)
  • 每日一题——三数之和(双指针)

    题目链接 思路 解析函数原型 首先我们来看一下题目给的函数原型: 题目要求我们 返回一个二维数组,数组的行数代表着存在多少个满足条件的三元组,而在本题中,列数规定为3,即每行存储3个元素 在螺旋矩阵中我们已经做过分析, nums就是题目给的整数数组,numsSize就是

    2024年02月07日
    浏览(37)
  • 2023-07-08 LeetCode每日一题(三数之和)

    点击跳转到题目位置 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不重复的三元组。 **注意:**答案中不可以包含重复的三元组。 提示: 3 = nums.length = 3000 -10 5

    2024年02月13日
    浏览(49)
  • 每日一题:LeetCode-LCR 007. 三数之和

    前言: 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈    🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉 算法 👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长

    2024年02月01日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包