题目:
难度:Middle
相关话题:数组
、哈希表
、双指针
给定一个包含n 个整数的数组 nums
和一个目标值 target
,判断 nums
中是否存在四个元素 a, b,c 和 d ,使得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]
]
思路:
时间复杂度O(N^3)
,3SUM
的基础上增加一个循环,参考NO.15
。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
nums.sort((a,b)=>a-b)
let res=[]
for(let i=0;i<nums.length-3;i++){
if(i>0 && nums[i]===nums[i-1])continue
for(let j=i+1;j<nums.length-2;j++){
if(j>i+1 && nums[j]===nums[j-1])continue
let targ=target-(nums[i]+nums[j])
let lo=j+1,hi=nums.length-1
while(lo<hi){
let sum=nums[lo]+nums[hi]
if(sum>targ){
hi--
}else if(sum<targ){
lo++
}else{
res.push([nums[i],nums[j],nums[lo],nums[hi]])
while(nums[lo]===nums[lo+1])lo++
while(nums[hi]===nums[hi-1])hi--
lo++
hi--
}
}
}
}
return res
};
扩展阅读: