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

news/2024/7/24 13:37:27/

❓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;}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 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—力扣专栏,每日更新!

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


http://www.ppmy.cn/news/193823.html

相关文章

通过网页免费下载音乐(F12)

找到你想要下载的音乐 1、按F12 2、点击网络或Network 3、按F5刷新 4、点击播放 5、找MP4文件 找到后双击

如何实现点击下载文件

Window.open(url) 优点&#xff1a;兼容性较好&#xff0c;兼容所有主流浏览器 缺点&#xff1a;会打开一个新的空白页面&#xff0c;并立即关闭 Window.location.hrefurl 优点&#xff1a;兼容性较好&#xff0c;兼容所有主流浏览器&#xff08;建议使用此方法&#x…

如何点击链接下载文件

<a href"/user/123/xxxx.txt" download"文件名.txt">点击下载</a>或者 <a href"/user/123/xxxx.txt" download>点击下载</a>

js实现点击按钮下载文件

其实就是创建一个a标签&#xff0c;设置a标签 download属性&#xff0c;只是用js的方式使用 var $a document.createElement(a);$a.setAttribute("href", src);$a.setAttribute("download", "");var evObj document.createEvent(MouseEvents);…

软件下载地址链接收藏

MYSQL下载链接地址 http://downloads.mysql.com/archives/get/file/mysql-5.1.40-linux-i686-icc-glibc23.tar.gz 官网地址&#xff1a;http://dev.mysql.com/downloads/ Apache&#xff08;HTTPd&#xff09;下载地址: http://mirrors.hust.edu.cn/apache/httpd/httpd-2.2.31…

实现点击按钮下载文档到本地

html <el-buttontype"primary"style"margin-right: 15px"click"downloadTemplate"size"mini">下载</el-button>js methods: {downloadTemplate() {const a document.createElement("a");a.href "/stati…

点击链接下载文件

//项目代码仅供参考downLoad(row) {const a document.createElement("a");const url process.env.VUE_APP_BASE_API row.fileUrl.slice(4); // 完整的url则直接使用&#xff0c;process.env.VUE_APP_BASE_API是项目地址&#xff0c;链接前缀此处拼接console.log(u…

免费下载网页文档

遇到需要收费的文档&#xff0c;在浏览器空白位置右击检查&#xff0c;然后点击下方图片右上角的设置按钮。 点击后&#xff0c;找到调试程序&#xff0c;勾选禁用JavaScript&#xff0c;再复制文档&#xff0c;就可以了

JS实现点击下载功能

JS实现点击下载功能 当我们拿到的数据只有路径的时候列如 我们可以直接这样操作 var link document.createElement(a)//构建一个a标签link.href row.filePath//把路径给它link.download row.title//下载的文件名字link.click()//模拟点击就实现了下载

点击下载

<el-button type"primary" size"medium" click"down" id"get">下载指令</el-button>down () {var myFrame document.createElement(iframe);myFrame.src 接口myFrame.style.display none;document.body.appendChild(my…

17素材网手动免费下载素材

1、随机打开想要下载的素材 2、点击查看演示&#xff0c;进入演示界面 3、右上角&#xff0c;X掉系统提示 4、按F12&#xff0c;进入开发者工具&#xff0c;我使用的是谷歌浏览器&#xff0c;默认是在右侧&#xff0c;可以调整位置 5、点击Sources&#xff0c;就可以看到当前…

【HTML】点击直接下载文件

1、使用<a>标签 <a href"/user/test/xxxx.txt" download"文件名.txt">点击下载</a>这样当用户打开浏览器点击链接的时候就会直接下载文件。 但是有个情况&#xff0c;比如txt,png,jpg等这些浏览器支持直接打开的文件是不会执行下载任务…

js通过点击实现文件下载

一般情况下通过a标签可以实现下载效果&#xff0c;比如一般的文件类的&#xff0c;但是如果是图片则大部分的浏览器都会跳转的一个页面进行显示图片&#xff0c;而不是下载。下面我们来介绍一个通用的文件下载方法。 html部分代码 <button οnclick"download(img/12.…

a 链接点击下载

1. 将链接设置为.zip 结尾2.在a元素中添加download 属性,&#xff08;目前只有chrome、firefox和opera支持&#xff09; function download(src) { var $a $("<a></a>").attr("href", src).attr("download", "img.png");…

pc端点击按钮下载app

一般 PC 端都会有这样一个下载 app 的按钮&#xff0c;举例哈 按钮对应的 html&#xff0c;样式肯定都会 <div class"x-download" click"downloadAPP"><div><div>立即下载</div><div>Android</div></div><d…

【懒人神器】鼠标自动连续点击器免费下载

软件介绍 鼠标自动连续点击器可以实现全自动点击鼠标、您可以自己设置点击类型、频率、以及开启/关闭点击热键&#xff0c;合适用在需要大量点击鼠标的地方、解放您的双手&#xff01;是工作娱乐的好帮手。 软件演示 软件特色 支持鼠标左键、右键选择 支持鼠标单击、双击选…

精品免费软件更新下载

腾讯QQ 2005 贺岁版 软件类别&#xff1a; 国产软件 / 免费版 / OICQ专区 文件大小&#xff1a; 17770 KB 运行环境&#xff1a; Win9x/NT/2000/XP 软件语言&#xff1a; 简体中文 软件等级&#xff1a; 在线注册&#xff1a; 点击这里进入注册中心> 开 发 商&am…

JS实现点击下载

<meta http-equiv"Content-Type" content"text/html; charsetutf-8" /> <a href"a.txt" idpic1 οnclick"savepic();return false;" style"cursor:hand">点击下载</a> <script> func…

Hackbar 免费下载+使用指南

hackbar收费了&#xff0c;破解的之前试过很早就失效了&#xff0c;很多插件网站也下架了。 我找了很久…不希望你也这么辛苦 Hackbar 免费下载使用指南 一、整理好的免费下载二、使用指南 一、整理好的免费下载 Firefox 下载:https://wws.lanzous.com/iDcdSfycpxe 密码:h0rh G…

点击下载文件

下面介绍的是使用 a 标签 "href"&#xff1a;文件地址 <a href"/user/test/xxxx.txt">点击下载</a> 由于.txt&#xff0c;.png&#xff0c;.jpg会直接打开&#xff0c;所以这之类后缀的文件 需要换一种写法 <a href"/user/test/xxxx…