专栏首页算法半岛LeetCode-18 四数之和

LeetCode-18 四数之和

↑点击上面"算法半岛"

关注"算法半岛"第一时间接收最新文章

> 题目:18. 四数之和

> 难度:中等

> 分类:数组

> 解决方案:双指针

今天我们学习第18题四数之和,这是一道中等题。像这样数组的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这道题的题目描述。

题目描述

给定一个包含 n个整数的数组 nums和一个目标值 target,判断 nums 中是否存在四个元素 abcd ,使得 a+b+c+d的值与 target相等?找出所有满足条件且不重复的四元组。

注意:答案中不可以包含重复的四元组。

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
满足要求的四元组集合为:
[
 [-1, 0, 0, 1],
 [-2, -1, 1, 2],
 [-2, 0, 0, 2]
]

分析

在前面,我们做过LeetCode-1 两数之和LeetCode-15 三数之和,这个题目是求四数之和,其基本思路和三数之和差不多,只是在三数之和的基础上增加一个 for循环。具体求解过程详见LeetCode-15 三数之和java代码如下所示:

class Solution {
 public List<List<Integer>> fourSum(int[] nums, int target) {
 List<List<Integer>> res = new ArrayList<List<Integer>>();
 if(nums == null && nums.length < 4)
 return res;
 // 对数组排序
 Arrays.sort(nums);
 // 固定第一个数
 for(int i=0; i<nums.length-3; ++i){
 if(i!=0 && nums[i] == nums[i-1]) 
 continue;
 if(nums[i+1]>0 && nums[i] >= target)
 return res;
 // 固定第二个数
 for(int j=i+1; j<nums.length-2; ++j){
 if((j != i + 1) && nums[j] == nums[j-1]) 
 continue;
 // 使用左右指针进行查找
 int left = j+1, right = nums.length-1;
 while(left < right){
 int sum = nums[i] + nums[j] + nums[left] + nums[right];
 if(sum == target){
 ArrayList<Integer> tmp = new ArrayList<Integer>();
                        tmp.add(nums[i]);
                        tmp.add(nums[j]);
                        tmp.add(nums[left]);
                        tmp.add(nums[right]);
                        res.add(tmp);
 ++left;
 --right;
 while(left<right && nums[left] == nums[left-1])
 ++left;
 while(left<right && nums[right] == nums[right+1])
 --right;
 }else if(sum > target)
 --right;
 else
 ++left;
 }
 }
 }
 return res;
 }
}

Github地址

LeetCode-18 四数之和 :https://github.com/JacobLei/leetcode/blob/master/src/main/java/A18_4Sum.java

参考链接

四数之和:https://leetcode-cn.com/problems/4sum/

本文分享自微信公众号 - 算法半岛(jacob2359)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你真的知道链表和数组的区别吗?

    对一名程序猿来讲,使用哪种语言来开发程序不是最重要的,数据结构和算法才是核心,是程序猿的内功,最终决定你的技术上限。如果你想拔高自己的水平,提高核心竞争力,数据...

    用户1260737
  • Shell脚本实现监控swap空间使用情况和查看占用swap的进程

    Shell脚本实现监控swap空间使用情况和查看占用swap的进程,曾经有一段时间机器的swap不停上涨,监控后发现是一些java进程占用swap空间后,完全不...

    菲宇
  • Dubbo for Go,Ready for Now.

    多语言支持是 Dubbo 发展生态的重点之一。目前,Dubbo 已经支持 PHP/Node.js/Python,同时,基于标准的 Java REST API -...

    heidsoft
  • Spring Boot MyBatis 动态数据源切换、多数据源,读写分离

    项目地址: https://github.com/helloworlde/SpringBoot-DynamicDataSource

    JAVA葵花宝典
  • Redis常用技术-----流水线(Pipelined)

    在事务中Redis提供了队列,可以批量执行任务,这样性能就比较高,但使用multi...exec事务命令是有系统开销的,因为它会检测对应的锁和序列化命令。有时我...

    秃头哥编程
  • 重拾Kotlin(17)-异常

    和 Java 不同的是,Kotlin 中 throw 结构是一个表达式,可以作为另一个表达式的一部分来使用

    叶应是叶
  • 修改包名

    那么,在解包生成的目录下找到AndroidManifest.xml,着手修改package以及对应引用。

    HLQ_Struggle
  • Java程序员进阶笔记实操—大型网站架构技术之负载均衡详解(2)

    欢迎关注专栏:Java架构技术进阶。里面有大量batj面试题集锦,还有各种技术分享,如有好文章也欢迎投稿哦。

    慕容千语
  • 教妹学 Java:难以驾驭的多线程

    “二哥,上一篇《集合》的反响效果怎么样啊?”三妹对她提议的《教妹学 Java》专栏很关心。

    沉默王二
  • 你还在把Java当成Android官方开发语言吗?Kotlin了解一下!

    Kotlin 能够扩展一个类的新功能而无需继承该类,或者对任意的类使用像“装饰者(Decorator)”这样的设计模式。这些都是通过叫做“扩展(extensio...

    Android技术干货分享

扫码关注云+社区

领取腾讯云代金券