首页 > 试题广场 >

三数之和

[编程题]三数之和
  • 热度指数:221609 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一个有n个元素的数组S,S中是否有元素a,b,c满足a+b+c=0?找出数组S中所有满足条件的三元组。

数据范围:,数组中各个元素值满足
空间复杂度:,时间复杂度

注意:
  1. 三元组(a、b、c)中的元素必须按非降序排列。(即a≤b≤c)
  2. 解集中不能包含重复的三元组。
例如,给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10) 
示例1

输入

[0]

输出

[]
示例2

输入

[-2,0,1,1,2]

输出

[[-2,0,2],[-2,1,1]]
示例3

输入

[-10,0,10,20,-10,-40]

输出

[[-10,-10,20],[-10,0,10]]
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> result;
        sort(num.begin(), num.end());
        for(int i=0; i<num.size(); ++i)
        {
            if(i!=0 && num[i]==num[i-1])
                continue;
            int j=i+1;
            int k = num.size()-1;
            while(j<k)
            {
                if(num[i]+num[j]+num[k]==0)
                {
                    vector<int> temp{num[i],num[j],num[k]};
                    result.push_back(temp);
                    ++j;
                    while(j<k && num[j]==num[j-1])
                        ++j;
                }
                else if(num[i]+num[j]+num[k]<0)
                    ++j;
                else
                    --k;
            }
        }
        return result;
    }
};

发表于 2018-07-09 16:07:07 回复(1)
//回溯法轻松斩杀    
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);
        }
    }

发表于 2022-08-01 11:01:31 回复(0)
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;
    }
};

发表于 2021-11-26 13:14:55 回复(0)
/**
 * 
 * @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题解没人写,我来一个,啊哈哈哈!
发表于 2021-09-26 13:09:56 回复(2)
思路:双指针
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        //双指针
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> ans=new ArrayList<ArrayList<Integer>> ();
        for(int i=0;i<num.length-2;i++){
            if(i!=0&&num[i]==num[i-1]) continue;
            int left=i+1;
            int right=num.length-1;
            while(left<right){
                if(num[i]+num[left]+num[right]==0) {
                    ArrayList<Integer> list=new ArrayList<> ();
                    list.add(num[i]);
                    list.add(num[left]);
                    list.add(num[right]);
                    ans.add(list);
                    left++;
                    right--;
                    while(left<right&&num[left]==num[left-1]) left++;
                    while(left<right&&num[right]==num[right+1]) right--;
                }
                if(num[i]+num[left]+num[right]<0) left++;
                if(num[i]+num[left]+num[right]>0) right--;
                
                
            }
        }
        return ans;
    }
}
发表于 2021-03-15 10:37:51 回复(0)
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;
    }
}
发表于 2019-11-04 10:49:39 回复(0)
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

发表于 2018-09-09 15:59:42 回复(0)
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;
    }
};
发表于 2018-06-04 11:00:39 回复(0)
 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;

发表于 2017-11-05 21:17:59 回复(0)
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;
    }
};

发表于 2017-10-03 01:38:27 回复(0)
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;
    }
};

发表于 2017-08-06 10:10:16 回复(0)
先排序,然后左右夹逼
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > result;
        if(num.size() < 3) return result;
        sort(num.begin(),num.end());
        const int target = 0;
        auto last = num.end();
       
        for(auto i=num.begin(); i<last-2; i++){
            auto j = i + 1;
            if(i > num.begin() && *i == *(i-1)) continue;
            auto k = last - 1;
            while(j < k){
                if(*i + *j + *k < target){
                    j++;
                    while(*j ==*(j-1) && j < k) j++;
                }else if(*i + *j + *k > target){
                    k--;
                    while(*k == *(k+1) && j < k) k--;
                }else{
                    result.push_back({*i , *j, *k});
                    j++;
                    k--;
                    while(*j == *(j-1) && *k == *(k+1) && j<k) j++;
                }
            }
        }
        return result;
    }
};
发表于 2016-06-28 09:05:09 回复(0)
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;
        
    }
    

};

发表于 2018-04-04 11:57:01 回复(3)
/**
 * (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;
    }
};

发表于 2016-06-13 16:24:47 回复(7)
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;
    }
}
编辑于 2017-08-12 14:29:26 回复(7)
这个也不对吗?题目中没要求子数组的顺序吧。
发表于 2022-03-03 15:23:24 回复(6)
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;
    }
};

发表于 2017-07-13 14:58:10 回复(0)
// 程序可以用来解决多个数求和等于给定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();
        }
        
    }
};

发表于 2018-06-28 10:02:28 回复(3)
怎么都在秀代码, 没有说话的啊
发表于 2022-06-22 08:51:36 回复(0)

先对数组进行排序,然后从第一个数开始固定,利用双指针从固定数后一个元素开始一头一尾进行对撞加和,判断和是否等于固定数的相反数

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
发表于 2022-05-19 15:08:29 回复(0)

问题信息

难度:
341条回答 28185浏览

热门推荐

通过挑战的用户