例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)
[0]
[]
[-2,0,1,1,2]
[[-2,0,2],[-2,1,1]]
[-10,0,10,20,-10,-40]
[[-10,-10,20],[-10,0,10]]
//回溯法轻松斩杀
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
ArrayList<Integer> path = new ArrayList<>();
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
Arrays.sort(num);
//去重
boolean[] flag = new boolean[num.length];
BackTracking(num, flag, 0);
return ans;
}
public void BackTracking(int[] num, boolean[] flag, int startindex) {
if (path.size() == 3) {
int sum = 0;
for (Integer i : path) {
sum += i;
}
if (sum == 0) ans.add(new ArrayList<>(path));
return;
}
//i不要忘了剪枝
for (int i = startindex; i < num.length - (3 - path.size()) + 1; i++) {
if (i > 0 && num[i] == num[i - 1] && !flag[i - 1]) continue;
path.add(num[i]);
flag[i] = true;
BackTracking(num, flag, i + 1);
flag[i] = false;
path.remove(path.size() - 1);
}
} 
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &nums) {
const int n = nums.size();
if (n < 3) return {};
sort(begin(nums), end(nums));
vector<vector<int>> sols;
for (int i = 0; i < n - 2; ++i) {
if (i and nums[i] == nums[i - 1]) continue;
int j = i + 1, k = n - 1;
while (j < k) {
if (nums[j] + nums[k] < -nums[i]) ++j;
else if (nums[j] + nums[k] > -nums[i]) --k;
else {
sols.push_back({nums[i], nums[j], nums[k]});
while (j < k and nums[j + 1] == nums[j]) ++j;
while (j < k and nums[k - 1] == nums[k]) --k;
++j, --k;
}
}
}
return sols;
}
}; 
/**
*
* @param num int整型一维数组
* @return int整型二维数组
*/
function threeSum( num ) {
// write code here
const ans=new Set()
let newNum=num.sort((a,b)=>{
return a-b
})
for(let i=0;i<newNum.length;i++){
let target=-newNum[i]
for(let j=i+1;j<newNum.length;j++){
if(newNum.indexOf(target-newNum[j],j+1)!==-1){
let index=num.indexOf(target-num[j])
let temp=[]
temp.push(num[i])
temp.push(num[j])
temp.push(num[index])
ans.add(temp)
while(num[j]==num[j+1]) j++ //去重
}
}
while(num[i]==num[i+1]) i++ //去重
}
return Array.from(ans)
}
module.exports = {
threeSum : threeSum
}; JS题解没人写，我来一个，啊哈哈哈！
import java.util.Arrays;
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
if (num == null || num.length == 0) {
return lists;
}
Arrays.sort(num);
for (int k = 0; k < num.length - 2; k++) {
if (num[k] > 0) {
break;
}
if (k > 0 && num[k] == num[k - 1]) {
continue;
}
int i = k + 1;
int j = num.length - 1;
while (i < j) {
int sum = num[k] + num[i] + num[j];
if (sum > 0) {
while (j > i && num[j] == num[--j]);
} else if (sum < 0) {
while (i < j && num[i] == num[++i]);
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(num[k]);
list.add(num[i]);
list.add(num[j]);
lists.add(list);
while (i < j && num[i] == num[++i]);
while (j > i && num[j] == num[--j]);
}
}
}
return lists;
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum { public static void main(String[] args) { threeSum(new int[]{1,-1,0}); } public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {
Arrays.sort(num);
int n=num.length;
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<n-2;i++){
if(i!=0&&num[i-1]==num[i]){
continue;
}
int start=i+1,end=n-1;
while(start<end){
if(num[i]+num[start]+num[end]==0){
List<Integer> asList = Arrays.asList(num[i],num[start],num[end]);
result.add(new ArrayList<Integer>(asList));
start++;end--;
while(start<end&&num[start]==num[start-1])start++;
while(start<end&&num[end]==num[end+1])end--;
}else if(num[i]+num[start]+num[end]>0){
end--;
while(start<end&&num[end]==num[end+1])end--;
}else{
start++;
while(start<end&&num[start]==num[start-1])start++;
}
}
} return result;
}
}
weileyigenvhaishuati 
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int>> res;
int sz=num.size();
if(sz<3)
return res;
unordered_multimap<int,pair<int,int>> co2;
unordered_multimap<int,int> co1;
for(int i=0;i<sz;i++)
{
co1.insert(make_pair(num[i],i));
for(int j=i+1;j<sz;j++)
co2.insert(make_pair(num[i]+num[j],pair<int,int>(i,j)));
}
for(auto i=co2.begin();i!=co2.end();i++)
{
int tp=(-1)*(i->first);
auto range=co1.equal_range(tp);
for(auto j=range.first;j!=range.second;j++)
{
int a=i->second.first;
int b=i->second.second;
int c=j->second;
if(a!=c&&b!=c)
{
vector<int> temp={num[a],num[b],num[c]};
sort(temp.begin(),temp.end());
res.push_back(temp);
}
}
}
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
return res;
}
};
vector<vector<int> > threeSum(vector<int> &num) {
sort(num.begin(),num.end());
vector<vector<int>> res;
vector<int> tmp;
int n=num.size();
for(int i=0;i<=n-3;i++){
int j=i+1;
int k=n-1;
if(i!=0&&num[i]==num[i-1])
continue;
while(i<k&&j<k){
if(num[j]+num[k]+num[i]<0)
j++;
else if(num[j]+num[k]+num[i]>0)
k--;
//(num[j]+num[k]==-num[i])
else{
tmp.push_back(num[i]);
tmp.push_back(num[j]);
tmp.push_back(num[k]);
res.push_back(tmp);
tmp.clear();
while(j<k&&num[j]==num[j+1]) j++;
while(j<k&&num[k]==num[k-1]) k--;
j++;
k--;
}
}
}
return res;
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) { int len = num.size(); vector<vector<int> > result; sort(num.begin(), num.end()); for(int i=0;i<len;i++) { if(i==0 || num[i]!=num[i-1]) { int l = i+1, r = len-1; while(l < r) { while(l<r && num[i]+num[l]+num[r]>0) r--; if(l<r && num[i]+num[l]+num[r]==0) { vector<int> v(3); v[0] = num[i]; v[1] = num[l]; v[2] = num[r]; result.push_back(v); while(l<r && num[l]==v[1]) l++; }else l++; } } } return result;
}
};
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > ans;
sort(num.begin(),num.end());
for(int i=0;i+2<num.size();i++){
int l=i+1,r=num.size()-1;
while(l<r){
while(l<r&&num[i]+num[l]+num[r]>0) r--;
if(l==r) break; //注意判断下相等的时候break。
if(num[i]+num[l]+num[r]==0){
ans.push_back(vector<int>{num[i],num[l],num[r]});
while(l<r&&num[l+1]==num[l]) l++;
}
l++;
}
while(i+1<num.size()&&num[i+1]==num[i]) i++;
}
return ans;
}
}; 
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int len = nums.size();
for(int k = 0; k < len; ++k){
if(nums[k] > 0)
break;
if(k > 0 && nums[k] == nums[k-1])
continue;
int tmp = -nums[k];
int i = k+1;
int j = len-1;
while(i < j){
if(nums[i] + nums[j] == tmp){
res.push_back({nums[k], nums[i], nums[j]});
while(i < j && nums[i] == nums[i+1])++i;
while(i < j && nums[j] == nums[j-1])--j;
++i; --j;
}else if(nums[i] + nums[j] < tmp){
++i;
}else if(nums[i] + nums[j] > tmp){
--j;
}
}
}
return res;
}
};
/**
* （1）首先对数组进行排序（从小到大）
* （2）依次取出第 i 个数（i从0开始），并且不重复的选取（跳过重复的数）
* （3）这样问题就转换为 2 个数求和的问题（可以用双指针解决方法）
* 2 数求和问题
* （4）定义两个指针：左指针（left） 和 右指针（right）
* （5）找出固定 left， 此时left所指的位置为数组中最小数，再找到两个数和 不大于 target 的最大 right 的位置
* （6）调整 left 的位置（后移），求解和是否为 target O(n)
* （7）时间复杂度：O(nlogn) + O(n)
*/
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
//数组排序（小-->大）
sort(num.begin(), num.end());
//结果集合
vector<vector<int>> ans;
//先依次取出一个数，转换为 2 数求和问题
for (int i = 0; i < num.size(); i++){
if ( i == 0 || num[i] != num[i-1]){//防止重复
//定义左右指针
int left = i + 1, right = num.size() - 1;
// 2 数求和问题，固定left， 找出最大的right
while (left < right){
//right 左移， 减小 num[right] 的值
while (left < right && num[i] + num[left] + num[right] > 0) right --;
if (left < right && num[i] + num[left] + num[right] == 0){
//保存当前结果
vector<int> temp(3);
temp[0] = num[i];
temp[1] = num[left];
temp[2] = num[right];
//保存到最终的结果中
ans.push_back(temp);
//右移 left （去除重复）
while (left < right && num[left] == temp[1]) left ++;
} else { // num[i] + num[left] + num[right] < 0的情况，left右移，增大num[left]的值
left++;
}
}
}
}
return ans;
}
};
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
int[] num = {-2, 0, 1, 1, 2};
System.out.println(new Solution().threeSum(num));
}
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (num == null) {
return result;
}
//排序
Arrays.sort(num);
int sum, left, right;
for (int i = 0; i < num.length - 2; i++) {
//避免重复, 比如前面计算了以-1开头,后面就不用计算了
if (i != 0 && num[i] == num[i - 1]) {
continue;
}
left = i + 1;
right = num.length - 1;
/**
* 固定一个数,从后面的数中选出两个数,因为数组是有序的,所以可以
* 用两个数组下标left和right,left指向当前元素的后一个位置,right指向最后一个位置
* 三个数相加的和等于0时,加入解集;
* 小于0时,把left往右边移动;
* 大于0时,把right往左边移动;
*/
while (left < right) {
sum = num[left] + num[right];
if (sum + num[i] == 0) {
ArrayList<Integer> solution = new ArrayList<>();
solution.add(num[i]);
solution.add(num[left]);
solution.add(num[right]);
result.add(solution);
left++;
right--;
//这个优化必须加,不加时间超限,其实这个优化也没太大作用嘛
while (left < right && num[left] == num[left - 1]) {
left++;
}
while (left < right && num[right] == num[right + 1]) {
right--;
}
} else if (sum + num[i] < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
}
这个也不对吗？题目中没要求子数组的顺序吧。
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num)
{
/// 先排序再双指针进行夹逼
int len = num.size();
vector<vector<int>> res;
if(len==0) return res;
sort(num.begin(),num.end());
for(int i=0;i<len;i++)
{
int sum = -num[i];
int j=i+1,k=len-1;
while(j<k)
{
int cur = num[j] + num[k];
if(cur==sum)
{
vector<int> temp;
temp.push_back(num[i]);
temp.push_back(num[j]);
temp.push_back(num[k]);
res.push_back(temp);
/// skip same num[j],num[k]
while(j<k && num[j]== temp[1])
j++;
while(j<k && num[k]== temp[2])
k--;
}
else if(cur<sum)
++j;
else
--k;
}
/// skip same num[i]
while(i<len-1 && num[i]== num[i+1])
i++;
}
return res;
}
};
// 程序可以用来解决多个数求和等于给定target的问题
// 使用的是DFS思想， 从左到右不断选择一个数，选择一条完整的路径并判断是否等于target
// 使用了剪枝来加快速度
// 对于重复的问题，使用的是set来对vector<int>型的变量去重
// （比unique那种要快，而且不需要对结果重新排序）
// 为了避免DFS造成的大量的空间占用，传递都为引用类型，需要恢复现场（push和pop）
class Solution {
int N = 3;
public:
// 使用DFS的思想来完成
vector<vector<int> > threeSum(vector<int> &num, int target=0) {
vector<vector<int>> result;
set<vector<int>> res;
vector<int> vi;
sort(num.begin(), num.end());
dfs(res, vi, num, target, 0, 0);
// sort(result.begin(), result.end());
// result.erase(unique(result.begin(),result.end()),result.end());
for(auto a:res){
result.push_back(a);
}
return result;
}
void dfs(set<vector<int>> &res, vector<int> &vi, vector<int> &num, int target, int start, int cnt) {
if(cnt==N){
if(target==0){
res.insert(vi);
}
return;
}
// 选择一个开始位置
for(int i=start;i<num.size();++i){
// cnt表示已经累加的数， 加上当前数的话， 还有n-cnt-1个数
// 所需要的是target-num[i]， 这个数一定要大于(N-cnt-1)*num[i])才行
if(target-num[i]<(N-cnt-1)*num[i]){
break;
}
// 选择了某条通路
vi.push_back(num[i]);
// 在该通路上继续前行
dfs(res,vi, num, target-num[i] , i+1, cnt+1);
// 恢复现场， 走完了某条通路， 需要恢复现场
vi.pop_back();
}
}
};
先对数组进行排序，然后从第一个数开始固定，利用双指针从固定数后一个元素开始一头一尾进行对撞加和，判断和是否等于固定数的相反数
class Solution:
def threeSum(self , num: List[int]) -> List[List[int]]:
n = len(num)
if n <= 2:
return []
res = []
num.sort()
for i in range(n):
if i != 0 and num[i] == num[i-1]:
continue
low = i + 1
high = n - 1
while low < high:
if num[low] + num[high] == -num[i]:
res.append([num[i], num[low], num[high]])
while low + 1 < high and num[low] == num[low+1]:
low += 1
while high - 1 > low and num[high] == num[high-1]:
high -= 1
low += 1
high -= 1
elif num[low] + num[high] > -num[i]:
high -= 1
else:
low += 1
return res
class Solution: def threeSum(self , num ): # write code here len_num=len(num) if len_num<3: return [] lis1=[] lis2=[] for i in range(len_num-2): a=num[i] for j in range(i+1,len_num-1): b=num[j] c=a+b if -c in num[j+1:]: lis2=sorted([a,b,-c]) if lis2 not in lis1: lis1.append(lis2) return sorted(lis1)
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
