LeetCode 15 3Sum AND 16 3Sum Closest AND 18 4Sum

题目链接:3Sum

题意:给一个数组,找出所有不同的三元组(a,b,c),满足a+b+c=0

 

对于K-Sum问题( \(\sum^K_i a_i = 0\) )都有通解

先对数组排序,再枚举 \(K-2\) 个数的和 \(sum\) ,再用二指针在 \(O(n)\) 时间求出剩下2个数 \((a,b)\) 满足 \(a+b=-sum\) ,所以复杂度为 \(O(n^{k-1})\)

对于去重,因为数组有序,所以可以直接跳过重复的数。同时注意左指针的起始位置。

时间复杂度 \(O(n^2)\)

 

 

 

题目链接:3Sum Closest

题意:给一个数组,找出一个三元组(a,b,c)的和sum=a+b+c,满足sum最接近给出的target

 

方法和上一道题差不多,每次移动指针更新答案

时间复杂度 \(O(n^2)\)

 

 

题目链接:4Sum

题意:给一个数组和target,找出所有的一个四元组(a,b,c,d)满足a + b + c + d = target

 

同理,先对数组排序,再枚举两个数的和,然后用二指针处理剩下两个数,注意利用大小关系去重

时间复杂度 \(O(n^3)\)

 

 

Categories: LeetCode