2506 字
约 8 分钟
22
LeetCode刷题Java版018.四数之和
2026-09-19
数据结构与算法
无标签

LeetCode刷题Java版018.四数之和

作者：沉默王二
发布时间：2022-08-04T23:25:18.204+0800

018.四数之和

题意

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

难度

中等

示例

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

分析

依旧是熟悉的配方，在经历了001.两数之和、015.三数之和，终于来到了久违的四数之和。

有了015.三数之和的定一移二的经验后，对于四数之和，我们也可以照葫芦画瓢（高雅一点的词汇叫举一反三），排序之后定二移二，遍历nums[i],nums[j]（i = 0;i < nums.length - 3;j = i + 1;j < nums.length - 2），移动 lef, rig （lef = j + 1,rig = nums.length - 1），从而找出和 target 最相近的值（目标答案）即可。

ava
class Solution {
public List<List> fourSum(int[] nums, int target) {
List<List> res = new ArrayList<>();
if(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;
for(int j = i + 1;j < nums.length - 2;j++){
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int lef = j + 1,rig = nums.length - 1;
while(lef < rig){
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] < (long)target)
lef++;
else
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] == (long)target){
res.add(Arrays.asList(nums[i],nums[j],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;rig--;
}
else
rig--;
}
}
}
return res;
}
}

但是很显然，这样的题解并不能确保我们领先很多其他同样在努力的LeetCode人，我们要优化！我们要领先！我们要最优解！

。。。。。。（表示思考中🤔）

首先我们可以考虑对前四个数字的大小进行判断，如果前四个就大于target，那么显然，后面是不可能有与target 相等的值，或者拿第一个数字与后三个数字比较，如果小于，显然第一个数字就太小，可以直接跳过。

所以……

ava
class Solution {
public List<List> fourSum(int[] nums, int target) {
List<List> res = new ArrayList<>();
if(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((long)nums[i] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < (long)target)
continue;
if((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > (long)target)
break;
for(int j = i + 1;j < nums.length - 2;j++){
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int lef = j + 1,rig = nums.length - 1;
while(lef < rig){
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] < (long)target)
lef++;
else
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] == (long)target){
res.add(Arrays.asList(nums[i],nums[j],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;rig--;
}
else
rig--;
}
}
}
return res;
}
}

总结

本道题中规中矩，有了前面的铺垫，这道题目应该被分为简单题（送分题，😜），而并非中等题，但考虑到有同学并没有做过前面的题目，所以列为中等题也不是不能接受。当然了，即使做过前面的题目，在面对这道题目的时候，我们仍然要想办法，怎样才能让我们的程序更加高效地运行，找出最优解。

力扣链接：https://leetcode.cn/problems/4sum/ 

    ## 018.四数之和

题意

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

难度

中等

示例

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

分析

依旧是熟悉的配方，在经历了001.两数之和、015.三数之和，终于来到了久违的四数之和。

有了015.三数之和的定一移二的经验后，对于四数之和，我们也可以照葫芦画瓢（高雅一点的词汇叫举一反三），排序之后定二移二，遍历nums[i],nums[j]（i = 0;i < nums.length - 3;j = i + 1;j < nums.length - 2），移动 lef, rig （lef = j + 1,rig = nums.length - 1），从而找出和 target 最相近的值（目标答案）即可。

ava
class Solution {
public List<List> fourSum(int[] nums, int target) {
List<List> res = new ArrayList<>();
if(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;
for(int j = i + 1;j < nums.length - 2;j++){
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int lef = j + 1,rig = nums.length - 1;
while(lef < rig){
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] < (long)target)
lef++;
else
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] == (long)target){
res.add(Arrays.asList(nums[i],nums[j],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;rig--;
}
else
rig--;
}
}
}
return res;
}
}

但是很显然，这样的题解并不能确保我们领先很多其他同样在努力的LeetCode人，我们要优化！我们要领先！我们要最优解！

。。。。。。（表示思考中🤔）

首先我们可以考虑对前四个数字的大小进行判断，如果前四个就大于target，那么显然，后面是不可能有与target 相等的值，或者拿第一个数字与后三个数字比较，如果小于，显然第一个数字就太小，可以直接跳过。

所以……

ava
class Solution {
public List<List> fourSum(int[] nums, int target) {
List<List> res = new ArrayList<>();
if(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((long)nums[i] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < (long)target)
continue;
if((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > (long)target)
break;
for(int j = i + 1;j < nums.length - 2;j++){
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int lef = j + 1,rig = nums.length - 1;
while(lef < rig){
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] < (long)target)
lef++;
else
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] == (long)target){
res.add(Arrays.asList(nums[i],nums[j],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;rig--;
}
else
rig--;
}
}
}
return res;
}
}

总结

本道题中规中矩，有了前面的铺垫，这道题目应该被分为简单题（送分题，😜），而并非中等题，但考虑到有同学并没有做过前面的题目，所以列为中等题也不是不能接受。当然了，即使做过前面的题目，在面对这道题目的时候，我们仍然要想办法，怎样才能让我们的程序更加高效地运行，找出最优解。

力扣链接：https://leetcode.cn/problems/4sum/
## 018.四数之和

题意

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

难度

中等

示例

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

分析

依旧是熟悉的配方，在经历了001.两数之和、015.三数之和，终于来到了久违的四数之和。

有了015.三数之和的定一移二的经验后，对于四数之和，我们也可以照葫芦画瓢（高雅一点的词汇叫举一反三），排序之后定二移二，遍历nums[i],nums[j]（i = 0;i < nums.length - 3;j = i + 1;j < nums.length - 2），移动 lef, rig （lef = j + 1,rig = nums.length - 1），从而找出和 target 最相近的值（目标答案）即可。

ava
class Solution {
public List<List> fourSum(int[] nums, int target) {
List<List> res = new ArrayList<>();
if(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;
for(int j = i + 1;j < nums.length - 2;j++){
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int lef = j + 1,rig = nums.length - 1;
while(lef < rig){
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] < (long)target)
lef++;
else
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] == (long)target){
res.add(Arrays.asList(nums[i],nums[j],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;rig--;
}
else
rig--;
}
}
}
return res;
}
}

但是很显然，这样的题解并不能确保我们领先很多其他同样在努力的LeetCode人，我们要优化！我们要领先！我们要最优解！

。。。。。。（表示思考中🤔）

首先我们可以考虑对前四个数字的大小进行判断，如果前四个就大于target，那么显然，后面是不可能有与target 相等的值，或者拿第一个数字与后三个数字比较，如果小于，显然第一个数字就太小，可以直接跳过。

所以……

ava
class Solution {
public List<List> fourSum(int[] nums, int target) {
List<List> res = new ArrayList<>();
if(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((long)nums[i] + nums[nums.length - 3] + nums[nums.length - 2] + nums[nums.length - 1] < (long)target)
continue;
if((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > (long)target)
break;
for(int j = i + 1;j < nums.length - 2;j++){
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
int lef = j + 1,rig = nums.length - 1;
while(lef < rig){
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] < (long)target)
lef++;
else
if((long)nums[i] + nums[j] + nums[lef] + nums[rig] == (long)target){
res.add(Arrays.asList(nums[i],nums[j],nums[lef],nums[rig]));
while(lef < rig && nums[lef] == nums[lef + 1]) lef++;lef++;
while(lef < rig && nums[rig] == nums[rig - 1]) rig--;rig--;
}
else
rig--;
}
}
}
return res;
}
}

总结

本道题中规中矩，有了前面的铺垫，这道题目应该被分为简单题（送分题，😜），而并非中等题，但考虑到有同学并没有做过前面的题目，所以列为中等题也不是不能接受。当然了，即使做过前面的题目，在面对这道题目的时候，我们仍然要想办法，怎样才能让我们的程序更加高效地运行，找出最优解。

力扣链接：https://leetcode.cn/problems/4sum/ 

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412
LeetCode刷题Java版018.四数之和
https://clxhxhhr.top/posts/2572/
作者
clxstart
发布于
2026-09-19
许可协议
CC BY-NC-SA 4.0
LeetCode刷题Java版：017.电话号码的字母组合
LeetCode刷题Java版019.删除链表的倒数第 N 个节点
评论
0 条
还没有评论，先写一条吧。