算法题丨4Sum
描述
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
示例
Given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
算法分析
难度:中
分析:给定整型数组和指定一个整型目标值,从整形数组中找出4个不同的元素,使得4个元素之和等于目标值,返回结果为所有满足上述条件的元素组合。
思路:思路可以参考3Sum,主要难度是由原先的找3个元素之和,变成了找4个元素之和。这种情况下,其实有点像解魔方:玩五阶魔方就是从五阶降到四阶,然后再从四阶降到三阶,最后再按照玩三阶魔方的方法解决问题。
最终的解法,其实就是在3阶解法的基础上,在外层再套一层4阶的循环,并做一些基础的判断,复杂度也是在3阶n²基础上*n=n³,当然,这种算法也可推广到n阶。
代码示例(C#)
public IList<IList<int>> FourSum(int[] nums, int target) { List<IList<int>> res = new List<IList<int>>(); if (nums.Length < 4) return res; //排序 Array.Sort(nums); //4阶判断 for (int i = 0; i < nums.Length - 3; i++) { //如果最近4个元素之和都大于目标值,因为数组是排序的,后续只可能更大,所以跳出循环 if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; //当前元素和最后3个元素之和小于目标值即本轮最大值都小于目标值,则本轮不满足条件,跳过本轮 if (nums[i] + nums[nums.Length - 1] + nums[nums.Length - 2] + nums[nums.Length - 3] < target) continue; //防止重复组合 if (i > 0 && nums[i] == nums[i - 1]) continue; //3阶判断 for (int j = i + 1; j < nums.Length - 2; j++) { //原理同4阶判断 if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; if (nums[i] + nums[j] + nums[nums.Length - 1] + nums[nums.Length - 2] < target) continue; int lo = j + 1, hi = nums.Length - 1; while (lo < hi) { //已知元素 nums[i],nums[j],剩下2个元素做夹逼 int sum = nums[i] + nums[j] + nums[lo] + nums[hi]; if (sum == target) { res.Add(new List<int> { nums[i], nums[j], nums[lo], nums[hi] }); while (lo < hi && nums[lo] == nums[lo + 1]) lo++; while (lo < hi && nums[hi] == nums[hi - 1]) hi--; lo++; hi--; } //两边夹逼 else if (sum < target) lo++; else hi--; } } } return res; }
复杂度
- 时间复杂度:O (n³).
- 空间复杂度:O (1).
附录
文章作者:原子蛋
文章出处:https://www.cnblogs.com/lizzie-xhu/
个人网站:https://www.lancel0t.cn/
个人博客:https://blog.lancel0t.cn/
微信公众号:原子蛋Live+
扫一扫左侧的二维码(或者长按识别二维码),关注本人微信公共号,获取更多资源。
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Java内存问题 及 LeakCanary 原理分析
前些天,有人问到 “开发过程中常见的内存泄漏都有哪些?”,一时脱口而出:静态的对象中(包括单例)持有一个生命周期较短的引用时,或内部类的子代码块对象的生命周期超过了外面代码的生命周期(如非静态内部类,线程),会导致这个短生命周期的对象内存泄漏。总之就是一个对象的生命周期结束(不再使用该对象)后,依然被某些对象所持有该对象强引用的场景就是内存泄漏。 这样回答很明显并不是问答人想要的都有哪些场景,所以这里抽时间整理了下内存相关的知识点,及LeakCanary工具的原理分析。 Java内存问题 及 LeakCanary 原理分析 在安卓等其他移动平台上,内存问题显得特别重要,想要做到虚拟机内存的高效利用,及内存问题的快速定位,了解下虚拟机内存模块及管理相关知识是很有必要的,这篇文章将从最基础的知识分析,内存问题的产生地方、原因、解决方案等原理。 一、运行时内存区域 这里以Java虚拟机为例,将运行时内存区分为不同的区域,每个区域承担着不同的功能。 方法区用户存储已被虚拟机加载的类信息,常量,静态常量,即时编译器编译后的代码等数据。异常状态 OutOfMemoryError,其中包含常量池和用...
- 下一篇
算法题丨Remove Element
描述 Given an array and a value, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn't matter what you leave beyond the new length. 示例 Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements of nums being 2. 算法分析 难度:低分析:给定数组和指定一个目标值,从数组中移除所有跟目标值相等的元素,返回最终元素的长度,注意不要...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS8编译安装MySQL8.0.19
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2整合Redis,开启缓存,提高访问速度
- CentOS关闭SELinux安全模块
- Hadoop3单机部署,实现最简伪集群
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2全家桶,快速入门学习开发网站教程
- SpringBoot2更换Tomcat为Jetty,小型站点的福音