- 题目描述：
- 设计思想：
-视频讲解链接B站视频讲解
- 复杂度分析：
- 代码： c++版本:
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> >res;//用于返回最后的结果
int n = num.size();//代表num的长度
sort(num.begin(),num.end());//排序用于双指针操作
for(int k = 0;k < n - 2;k ++){
/*
1）由于我们的k指向的是最小的数字，如果num[k]>0时直接break即可，
因为num[k] + num[i] + num[j] > 0一定成立
*/
if(num[k] > 0) break;
/*
由于题意说不要去找重复的三元组，如果num[k] == num[k-1]的时候，
我们可以跳过当前的num[k]因为我们已经早就将num[k-1]成立的结果加入结果集合了
*/
//记得要满足k-1是有效的
if(k > 0 && num[k] == num[k - 1]) continue;
int i = k + 1,j = n - 1;
while(i < j){
int sum = num[k] + num[i] + num[j];
if(sum < 0){
/*
当num[k] + num[i] + num[j] < 0 时，我们让i指针往右移动，
并跳过所有跟当前i相同的数字
*/
//移动i指针
while(i < j){
int index = i;
if(num[++ i] != num[index]) break;
}
}else if(sum > 0){
/*
当num[k] + num[i] + num[j] >0 时,我们让j指针往左移动，
并跳过所有跟当前j相同的数字
*/
//移动j指针
while(i < j){
int index = j;
if(num[-- j] != num[index]) break;
}
}else{
//插入结果
vector<int> tmp={num[k],num[i],num[j]};
res.push_back(tmp);
//移动i指针
while(i < j){
int index = i;
if(num[++ i] != num[index]) break;
}
//移动j指针
while(i < j){
int index = j;
if(num[-- j] != num[index]) break;
}
}
}
}
return res;
}
};
Java版本：
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();//用于返回最后的结果
int n = num.length;//代表num的长度
Arrays.sort(num);//排序用于双指针操作
for(int k = 0;k < n - 2;k ++){
/*
1）由于我们的k指向的是最小的数字，如果num[k]>0时直接break即可，
因为num[k] + num[i] + num[j] > 0一定成立
*/
if(num[k] > 0) break;
/*
由于题意说不要去找重复的三元组，如果num[k] == num[k-1]的时候，
我们可以跳过当前的num[k]因为我们已经早就将num[k-1]成立的结果加入结果集合了
*/
//记得要满足k-1是有效的
if(k > 0 && num[k] == num[k - 1]) continue;
int i = k + 1,j = n - 1;
while(i < j){
int sum = num[k] + num[i] + num[j];
if(sum < 0){
/*
当num[k] + num[i] + num[j] < 0 时，我们让i指针往右移动，
并跳过所有跟当前i相同的数字
*/
//移动i指针
while(i < j){
int index = i;
if(num[++ i] != num[index]) break;
}
}else if(sum > 0){
/*
当num[k] + num[i] + num[j] >0 时,我们让j指针往左移动，
并跳过所有跟当前j相同的数字
*/
//移动j指针
while(i < j){
int index = j;
if(num[-- j] != num[index]) break;
}
}else{
//插入结果
res.add(new ArrayList<Integer>(Arrays.asList(num[k],num[i],num[j])));
//移动i指针
while(i < j){
int index = i;
if(num[++ i] != num[index]) break;
}
//移动j指针
while(i < j){
int index = j;
if(num[-- j] != num[index]) break;
}
}
}
}
return res;
}
}
Python版本:
#
#
# @param num int整型一维数组
# @return int整型二维数组
#
class Solution:
def threeSum(self , num ):
# write code here
res = []#用于返回最后的结果
n = len(num)#代表num的长度
arr = num.sort()#排序用于双指针操作
for k in range(0,n - 2):
'''
1）由于我们的k指向的是最小的数字，如果num[k]>0时直接break即可，
因为num[k] + num[i] + num[j] > 0一定成立
'''
if(num[k] > 0): break
'''
由于题意说不要去找重复的三元组，如果num[k] == num[k-1]的时候，
我们可以跳过当前的num[k]因为我们已经早就将num[k-1]成立的结果加入结果集合了
'''
#记得要满足k-1是有效的
if(k > 0 and num[k] == num[k - 1]): continue
i = k + 1
j = n - 1
while(i < j):
sum = num[k] + num[i] + num[j]
if(sum < 0):
'''
当num[k] + num[i] + num[j] < 0 时，我们让i指针往右移动，
并跳过所有跟当前i相同的数字
'''
#移动i指针
while(i < j):
index = i
i += 1
if(num[i] != num[index]): break
elif(sum > 0):
'''
当num[k] + num[i] + num[j] >0 时,我们让j指针往左移动，
并跳过所有跟当前j相同的数字
'''
#移动j指针
while(i < j):
index = j
j -= 1
if(num[j] != num[index]): break
else:
#插入结果
res.append([num[k],num[i],num[j]])
#移动i指针
while(i < j):
index = i
i += 1
if(num[i] != num[index]): break
#移动j指针
while(i < j):
index = j
j -= 1
if(num[j] != num[index]): break
return res;
JavaScript版本:
/**
*
* @param num int整型一维数组
* @return int整型二维数组
*/
function threeSum( num ) {
// write code here
let res = [];//用于返回最后的结果
let n = num.length;//代表num的长度
let arr = num.sort(function(a,b){return a-b;})//排序用于双指针操作
for(let k = 0;k < n - 2;k ++){
/*
1）由于我们的k指向的是最小的数字，如果num[k]>0时直接break即可，
因为num[k] + num[i] + num[j] > 0一定成立
*/
if(num[k] > 0) break;
/*
由于题意说不要去找重复的三元组，如果num[k] == num[k-1]的时候，
我们可以跳过当前的num[k]因为我们已经早就将num[k-1]成立的结果加入结果集合了
*/
//记得要满足k-1是有效的
if(k > 0 && num[k] == num[k - 1]) continue;
let i = k + 1,j = n - 1;
while(i < j){
let sum = num[k] + num[i] + num[j];
if(sum < 0){
/*
当num[k] + num[i] + num[j] < 0 时，我们让i指针往右移动，
并跳过所有跟当前i相同的数字
*/
//移动i指针
while(i < j){
let index = i;
if(num[++ i] != num[index]) break;
}
}else if(sum > 0){
/*
当num[k] + num[i] + num[j] >0 时,我们让j指针往左移动，
并跳过所有跟当前j相同的数字
*/
//移动j指针
while(i < j){
let index = j;
if(num[-- j] != num[index]) break;
}
}else{
//插入结果
res.push([num[k],num[i],num[j]])
//移动i指针
while(i < j){
let index = i;
if(num[++ i] != num[index]) break;
}
//移动j指针
while(i < j){
let index = j;
if(num[-- j] != num[index]) break;
}
}
}
}
return res;
}
module.exports = {
threeSum : threeSum
};
京公网安备 11010502036488号