首页 > 试题广场 >

三数之和

[编程题]三数之和

热度指数：221611 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

数据范围： $0 \le n \le 1000$ ，数组中各个元素值满足 $|val | \le 100$

空间复杂度： $O(n^2)$ ，时间复杂度 $O(n^2)$

注意：

三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。

例如，给定的数组 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]]

算法知识视频讲解

Java

牛客624030975号

public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if (num.length < 3){
            return list;
        }
        Arrays.sort(num);
        for (int i = 1; i < num.length - 1; i++) {
            for (int j = 0; j < i; j++) {
                for (int k = i + 1; k < num.length; k++) {
                    if (num[i] + num[j] + num[k] == 0){
                        ArrayList<Integer> row = new ArrayList<>();
                        row.add(num[j]);
                        row.add(num[i]);
                        row.add(num[k]);
                        if (!list.contains(row)){
                            list.add(row);
                        }
                        break;
                    }
                }
            }
        }

        Collections.sort(list, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                int flag1 = o1.get(0) - o2.get(0);
                int flag2 = o1.get(1) - o2.get(1);
                if (flag1 == 0 && flag2 == 0){
                    return o1.get(2).compareTo(o2.get(2));
                } else if (flag1 == 0) {
                    return o1.get(1).compareTo(o2.get(1));
                }
                return o1.get(0).compareTo(o2.get(0));
            }
        });

        return list;
    }

编辑于 2023-12-16 19:09:29 回复(0)

Java

一大青枣

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param num int整型一维数组

* @return int整型ArrayList<ArrayList<>>

public ArrayList<ArrayList<Integer>> threeSum (int[] num) {

// write code here

ArrayList<ArrayList<Integer>> res=new ArrayList<>();

Set<ArrayList<Integer>> map=new HashSet<>();

if(num.length<3){

return res;

}

Arrays.sort(num);

for(int i=0;i<num.length;i++){

int l=i-1;int r=i+1;

while(l>=0 && r<num.length){

if(num[l]+num[r]+num[i]==0){

ArrayList<Integer> temp=new ArrayList<>();

temp.add(num[l]);

temp.add(num[i]);

temp.add(num[r]);

Collections.sort(temp);

if(!map.contains(temp)){

res.add(temp);

map.add(temp);

}

l--;r++;

}else if(num[l]+num[r]+num[i]<0){

r++;

}else{

l--;

}

//说实话，这个地方真的恶心，list里面的元素要排序就算了，题目里面又没有说这个二维list还要根据每一个list里面的元素大小再排一次序，不然就再那第十一个用例那报错，我也是服了。

Comparator<List<Integer>> comparator = (a, b) -> a.get(0).compareTo(b.get(0));

Collections.sort(res, comparator);

return res;

}

发表于 2023-09-17 14:22:13 回复(1)

Java

牛客781396821号

这样子时间复杂度总比暴力要低一些吧

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        // 将数组排序
        Comparator<Integer> cmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return a - b;
            }
        };
        Arrays.sort(num);
        int length = num.length;

        // 通过找到中间值，以此向两边扩散寻找的方法找到符合的数组
        for (int i = 0; i < length; i++) {
            int sum = num[i];
            int j = i - 1;
            int k = i + 1;
            for (; j >= 0 && k < length;) {
                int sum1 = sum + num[j] + num[k];
                if (sum1 < 0) {
                    k++;
                } else if (sum1 > 0) {
                    j--;
                } else {
                    ArrayList<Integer> r = new ArrayList<Integer>();
                    r.add(num[j]);
                    r.add(num[i]);
                    r.add(num[k]);
                    if (!result.contains(r)) {
                        result.add(r);
                    }
                    k++;
                    j--;
                }
            }
        }

        // 最后记得将结果排序
        Comparator<ArrayList<Integer>> cmp2 = new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> a, ArrayList<Integer> b) {
                if (a.get(0) != b.get(0)) return a.get(0) - b.get(0);
                if (a.get(1) != b.get(1)) return a.get(1) - b.get(1);
                return a.get(2) - b.get(2);
            }
        };
        result.sort(cmp2);

        return result;
    }
}

发表于 2023-08-19 18:21:46 回复(0)

Java

做则必成的勇气和信心

public ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        //三数之和用的不是map
        //用的是双指针
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        Arrays.sort(num);
        if(num==null||num.length==1) return ans;
        for(int i=0;i<num.length;i++){
            if(num[0]>0){
                return ans;
            }
            if(i>0&&num[i]==num[i-1]){
                continue;
            }
            int left=i+1;
            int right=num.length-1;
            while(left<right){//都是有效索引
                int sum=num[i]+num[left]+num[right];
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else{
                    ans.add(new ArrayList<>(Arrays.asList(num[i],num[left],num[right])));
                    while((left<right)&&(num[left]==num[left+1])) {left++;}
                    while((left<right)&&(num[right]==num[right-1])) {right--;}
                    left++;
                    right--;
                }
            }
        }
        return ans;
    }

发表于 2023-07-14 10:05:16 回复(0)

Java

牛客635452961号

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param num int整型一维数组

* @return int整型ArrayList<ArrayList<>>

public ArrayList<ArrayList<Integer>> threeSum (int[] num) {

Arrays.sort(num);

LinkedHashSet<ArrayList<Integer>> set = new LinkedHashSet<>();

for (int i = 0; i < num.length; i++) {

for (int j = i+1; j < num.length; j++) {

for (int k = j+1; k < num.length; k++) {

if (num[i]+num[j]+num[k]==0){

ArrayList<Integer> list = new ArrayList<>();

list.add(num[i]);

list.add(num[j]);

list.add(num[k]);

set.add(list);

}

ArrayList<ArrayList<Integer>> integerArrayList = new ArrayList<>(set);

return integerArrayList;

}

需要使用有序的set集合 LinkedHashSet来解决不然使用hashset答案集合的顺序会不一样

发表于 2023-07-11 02:47:09 回复(0)

Java

BlueProtocol

        if (num == null || num.length == 0 || (num.length == 1 &&
                                               num[0] == 0)) return new ArrayList<ArrayList<Integer>>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        int n = num.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if ((num[i] + num[j] + num[k]) == 0) {
                        ArrayList<Integer> list = new ArrayList<Integer>();
                        list.add(num[i]);
                        list.add(num[j]);
                        list.add(num[k]);
                        Collections.sort(list);
                        if (!res.contains(list))  {
                            res.add(list);
                        }
                    }
                }
            }
        }
        Collections.sort(res, (a, b)-> {
            if (a.get(0) == b.get(0)) {
                if (a.get(1) == b.get(1) )  {
                    return a.get(2) - b.get(2);
                } else return a.get(1) - b.get(1);
            } else {
                return a.get(0) - b.get(0);
            }

        });
        return res;

发表于 2023-07-03 21:37:20 回复(0)

Java

拒绝pua的小蜗牛很想潜水

import java.util.*;

public class Solution {

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {

ArrayList<ArrayList<Integer>> res = new ArrayList<>();

if (num.length < 3)return res;

Arrays.sort(num);

for (int i = 0; i < num.length; i++) {

if (i > 0 && num[i] == num[i - 1])continue;

int left = i + 1, right = num.length - 1;

while (left < right) {

int sum = num[i] + num[left] + num[right];

if (sum < 0)left++;

else if (sum > 0)right--;

else {

List<Integer> list = Arrays.asList(num[i], num[left], num[right]);

res.add(new ArrayList<>(list));

while (left < right && num[left] == num[left + 1])left++;

while (left < right && num[right] == num[right - 1])right--;

left++;

right--;

}

return res;

}

发表于 2023-04-19 15:58:08 回复(0)

Java

牛客330900603号

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        final int len = num.length;
        if (len < 3) {
            return new ArrayList<>();
        }
        //将其改为升序
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int i = 0; i < len - 2; i++) {
            //遍历每一个数，找另外两个数之和为当前数的相反数的即可
            //因为默认时按升序排列，所以说要找的另外两个数一定在当前数字的后边
            int current = num[i];
            int front = i + 1, rear = len - 1;
            if (i > 0 && num[i - 1] == num[i]) continue;
            while (front < rear) {
                if (num[front] + num[rear] == -current) {
                    ArrayList<Integer> list = new ArrayList<>(Arrays.asList(current, num[front],
                            num[rear]));
                    res.add(list);
                    //front++;
                    while (num[rear] == num[--rear]&&rear>0);//防止[0,0,0]越界
                    continue;
                }
                if (num[front + 1] + num[rear] > -current) {
                    rear--;
                } else {
                    while (num[front] == num[++front]&&front<len-1);//防止[-2,-1,-1]越界
                }
            }


        }

        return res;
    }
}

发表于 2023-02-28 13:11:49 回复(0)

Java

欧洲金靴

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        if (num.length < 2) {
            return new ArrayList<>();
        }
        int idx1 = 0, idx2 = 1, idx3 = 2;
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        while (idx1 <= num.length - 3) {
            int num1 = num[idx1];
            int num2 = num[idx2];
            int num3 = num[idx3];
            if (num1 + num2 + num3 == 0) {
                ArrayList<Integer> tmp = new ArrayList<>();
                tmp.add(num1);
                tmp.add(num2);
                tmp.add(num3);
                Collections.sort(tmp);
                if (!list.contains(tmp)) {
                    list.add(tmp);
                }
            }
            if (idx3 < num.length - 1) {
                idx3++;
            } else {
                idx2++;
                idx3 = idx2 + 1;
            }
            if (idx2 >= num.length - 2) {
                idx1++;
                idx2 = idx1 + 1;
                idx3 = idx2 + 1;
            }
        }
        return list;
    }
}

发表于 2023-01-30 17:59:16 回复(0)

Java

牛客52179931号

1.先排序，便于后面去重

2.使用3个指针，i从第一个位置开始，left从i+1开始向后移动，right从数组末尾开始向前移动

3.i去重，判断num[i] == num[i -1]

left去重：判断num[left] == num[left - 1]

right去重: 判断num[right] == num[right + 1]

过后再判断当前3个数之和，大于0时，right向前移动，小于0时，left向后移动。知道三数之和为0，将num[i]，num[left]，num[right]加入到链表中，因为已经排序了，所以顺序就是从小到大的。

import java.util.*;

public class Solution {

    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if (num.length < 3) {

            return result;

        }

        // 先排序便于后面去重

        for (int i = 0; i < num.length; i++) {

            for (int j = 0; j < num.length - i - 1; j++) {

                if (num[j] > num[j + 1]) {

                    int temp = num[j];

                    num[j] = num[j + 1];

                    num[j + 1] = temp;

                }

            }

        }

        for (int i = 0; i < num.length - 1; i++) {

            if (num[i] > 0) {

                break;

            }

            // 第一个位置的数字去重

            if (i > 0 && num[i] == num[i - 1]) {

                continue;

            }

            int left = i + 1;

            int right = num.length - 1;

            while (left < right) {

                // 中间数字去重

                if (left != i + 1 && num[left] == num[left - 1]) {

                    left++;

                    continue;

                }

                // 最后一个位置的数字去重

                if (right != num.length - 1 && num[right] == num[right + 1]) {

                    right--;

                    continue;

                }

                if (num[i] + num[left] + num[right] > 0) {

                    right--;

                } else if (num[i] + num[left] + num[right] < 0) {

                    left++;

                } else {

                    ArrayList<Integer> list = new ArrayList<>();

                    list.add(num[i]);

                    list.add(num[left]);

                    list.add(num[right]);

                    result.add(list);

                    left++;

                    right--;

                }

            }

        }

        return result;

    }

}

发表于 2022-11-02 20:26:46 回复(0)

Java

qzuser942

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int l = num.length;
        Arrays.sort(num);
        for (int n = 0; n < l; n++) {
            for (int i = 0, j = l - 1; i < j;) {
                if (i == n) {
                    i++;
                    continue;
                }
                if (j == n) {
                    j--;
                    continue;
                }

                if (num[n] + num[i] + num[j] > 0) {
                    j--;
                } else if (num[n] + num[i] + num[j] < 0) {
                    i++;
                } else {
                    ArrayList<Integer> re = new ArrayList<>();
                    re.add(num[n]);
                    re.add(num[i]);
                    re.add(num[j]);
                    Collections.sort(re);
                    if(!res.contains(re)){
                        res.add(re);
                    }
                    i++;
                    j--;
                }
            }
        }
        return res;
    }
}

发表于 2022-10-05 16:55:22 回复(0)

Java

小姜啥都不会

这个题里面有要求三元组之间的顺序吗？？？

发表于 2022-09-26 11:34:29 回复(1)

Java

北极以北_

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        Arrays.sort(num);

        for (int i = 0; i < num.length - 2; i++) {
            if (num[i] > 0) break;
            if (i > 0 && num[i] == num[i - 1]) continue;

            int j = i + 1, k = num.length - 1;
            while (j < k) {
                int sum = num[i] + num[j] + num[k];
                if (sum < 0) {
                    while (j < k && num[j] == num[++j]);
                } else if (sum > 0) {
                    while (j < k && num[k] == num[--k]);
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(num[i], num[j], num[k])));
                    while (j < k && num[j] == num[++j]);
                    while (j < k && num[k] == num[--k]);
                }
            }
        }
        return res;
    }

发表于 2022-09-20 16:21:07 回复(0)

Java

活泼的秋田犬给你点了个赞

import java.util.*;

public class Solution {

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {

ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();

if (num.length <= 2) {

return arrayLists;

}

Arrays.sort(num);

int sum, right, left;

for (int i = 0; i < num.length - 2; i++) {

if (i != 0 && num[i] == num[i - 1]) {

continue;

}

left = i + 1;

right = num.length - 1;

while (left < right) {

sum = num[left] + num[right];

if (sum + num[i] == 0) {

ArrayList<Integer> objects = new ArrayList<>();

objects.add(num[i]);

objects.add(num[left]);

objects.add(num[right]);

arrayLists.add(objects);

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 arrayLists;

}

发表于 2022-09-18 15:48:56 回复(0)

Java

勇敢牛牛不怕难

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        Arrays.sort(num);
        for(int i=0;i<num.length-2;i++){
            if(i>0&&num[i]==num[i-1]){
                continue;
            }
            //双指针，一头一尾
            int j=i+1;
            int k=num.length-1;
            ArrayList<Integer> temp=new ArrayList<>();
            while(j<k){
                int val=num[i]+num[j]+num[k];
                if(val==0){
                    temp.add(num[i]);
                    temp.add(num[j]);
                    temp.add(num[k]);
                    res.add(temp);
                    temp=new ArrayList<>();
                    //处理重复问题
                    do{
                        j++;
                    }while(j<k&&num[j]==num[j-1]);
                    
                    do{
                        k--;
                    }while(k>j&&num[k]==num[k+1]);
                    
                }else if(val>0){
                    //说明太大了
                    k--;
                }else{
                    //太小
                    j++;
                }
            }
            
        }
        return res;
    }
}

发表于 2022-08-28 18:53:21 回复(0)