首页 > 试题广场 >

三数之和

[编程题]三数之和

热度指数：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]]

算法知识视频讲解

查看答案及解析

Python3

喜欢唱跳rap安迪刷了100道题

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

# @param num int整型一维数组

# @return int整型二维数组

class Solution:

def threeSum(self , num: List[int]) -> List[List[int]]:

# write code here

d=dict.fromkeys(num,0)

out=[]

for i in num:

d[i] += 1

for i in d:

for j in d:

d[i] -= 1

d[j] -= 1

if d[i]>=0 and d[j]>=0 and d.get(-i-j):

if d[-i-j]>0:

temp=sorted((i,j,-i-j))

if temp not in out:

out.append(temp)

d[i] += 1

d[j] += 1

return sorted(out)

发表于 2023-09-27 23:30:39 回复(0)

Python3

此愿如愿

暴力解法：

class Solution:

def threeSum(self , num: List[int]) -> List[List[int]]:

tmp = []

new_list = sorted(num)

l_len = len(new_list)

for i in range(l_len):

if i + 2 <= l_len:

for j in range(i + 1, l_len):

for k in range(j + 1, l_len):

if num[i] + num[j] + num[k] == 0:

bb = sorted([num[i], num[j], num[k]])

# 去重

if bb not in tmp:

tmp.append(bb)

return sorted(tmp)

发表于 2023-06-01 15:08:38 回复(0)

Python3

pzq

# 哈希表
class Solution:
    def threeSum(self , num: List[int]) -> List[List[int]]:
        # 创建有重复key值的哈希表
        tab_hash = {}
        for ind, val in enumerate(num):
            if tab_hash.get(val) is not None:
                tab_hash[val] = tab_hash[val] + [ind]
            else:
                tab_hash[val] = [ind]
        print(tab_hash)
        # 查找
        res = []
        for ind1 in range(len(num)):
            for ind2 in range(ind1 + 1, len(num)):
                val = -1 * (num[ind1] + num[ind2])  #   求差值
                ind3_list = tab_hash.get(val, None)
                if ind3_list is not None:
                    for ind3 in ind3_list:  # 遍历索引
                        if ind3 not in [ind1, ind2]:    # 保证索引不相同
                            res1 = [num[ind1], num[ind2], num[ind3]]
                            res1.sort()
                            if res1 not in res: # 保证三元组不重复
                                res.append(res1)
        # 结果排序(多重排序)
        res.sort(key=lambda x: (x[0], x[1], x[2]))
        return res

发表于 2023-05-17 01:25:19 回复(0)

Python3

Namely

class Solution:
    def twoSum(self, num:List[int], target:int):
        print(num, target)
        ret = []
        i, j = 0, len(num) - 1
        while i<j:
            if num[i] + num[j] > target:
                j -= 1
            elif num[i] + num[j] < target:
                i += 1
            else:
                # 此处需要对结果做去重
                if [num[i], num[j]] not in ret:
                    ret.append([num[i], num[j]])
                i += 1
                j -= 1
        print(ret)   
        return ret

    # 先排序 再用两边夹的方式
    def threeSum(self , num: List[int]) -> List[List[int]]:
        ret = []
        m = len(num)
        if m < 3:
            return ret

        # 先排序
        num.sort()
        for e in range(m-2):
            target = 0 - num[e]
            # 此时退化为有序数组的twoSum
            ret1 = self.twoSum(num[e+1:], target)
            if len(ret1) > 0:
                # 此处需要对结果做去重
                ret += [k for k in [[num[e]] + l for l in ret1] if k not in ret]      
        return ret

发表于 2023-03-02 11:17:58 回复(0)

Python3

ajaxx

class Solution:
    def threeSum(self , num: List[int]) -> List[List[int]]:
        # write code here
        if len(num) < 3:
            return []
        help = {}
        res = []
        num = sorted(num)
        for i in range(len(num)-2):
            target = -num[i]
            l = i + 1
            r = len(num) - 1
            while l < r:
                if num[l] + num[r] == target:
                    res.append((num[i], num[l], num[r]))
                    res = list(set(res))
                    l += 1
                elif num[l] + num[r] < target:
                    l += 1
                else:
                    r -= 1
        return res

整体无序都能被判错吗有没有大佬帮忙看看哪里出问题啊谢谢

发表于 2022-12-30 17:53:17 回复(1)

Python3

求offer牛

class Solution:
    def is_same(self,lit,l):
        """
        lit:最终存储的可能数组
        l：可能的答案
        判断l是否已经存在，手动去重（可能时间要比代码里去重长）
        """
        for i in range(len(lit)):
            if lit[i] == l:
                return False
        return True
    def threeSum(self , num: List[int]) -> List[List[int]]:
        # write code here
        num.sort()
        n = len(num)
        res = []#存储最终数组
        for i in range(n-2):
            if num[i] <= 0:
                left = i+1
                right = n-1
                while left<right:
                    if num[left] + num[right] == abs(num[i]):
                        r = [num[i],num[left],num[right]]
                        if self.is_same(res,r):
                            res.append(r)
                        left +=1
                        right -= 1 
                    elif num[left] + num[right] < abs(num[i]):
                        left +=1
                    else:
                        right -= 1
            else:
                continue
        return res

发表于 2022-11-24 17:44:05 回复(0)

Python3

牛客867665296号

题目只要求：

1. 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c)

2. 解集中不能包含重复的三元组。

并没有要求三元组之间的顺序。

发表于 2022-10-10 15:15:39 回复(0)

Python3

JianYue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def threeSum(self , num: List[int]) -> List[List[int]]:
        ret = []
        length = len(num)
        if length < 3:
            return ret
        num.sort()
        cur = -10000
        for i in range(length):
            if cur == num[i]:
                continue
            else:
                cur = num[i]
            fir, sec = i+1, length-1
            while fir < sec:
                sum = num[fir] + num[sec] + cur
                if sum == 0:
                    ret.append([cur, num[fir], num[sec]])
                    while num[fir] + num[sec] + cur == 0 and fir < sec:
                        fir = fir + 1
                elif sum > 0:
                    sec = sec - 1
                elif sum < 0:
                    fir = fir + 1
        return ret

发表于 2022-09-25 16:36:00 回复(2)

Python3

E-Doz

class Solution:
    def threeSum(self , num: List[int]) -> List[List[int]]:
        # write code here
        def dfs(num, cur, ret):
            if len(cur) == 3:
                if sum(cur) == 0:
                    ret.append(cur)
                return
            if not num:
                return
            for i in range(len(num)):
                if i != 0 and num[i] == num[i-1]:
                    continue
                dfs(num[i+1:], cur+[num[i]],ret)
        ret = []
        num = sorted(num)
        dfs(num,[],ret)
        return ret

发表于 2022-09-17 22:15:18 回复(0)

Python3

Vivimore

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

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)

Python3

6666612

class Solution:
    def threeSum(self , num ):
        # write code here
        if len(num)<3:
            return []
        num.sort()
        if num[0] > 0:
            return []
        res = []
        lenth = len(num)
        for i in range(lenth):
            for left in range(i+1,lenth-1):
                for right in range(lenth-1,left,-1):
                    if right > left:
                        if num[i] + num[left] + num[right] == 0:
                            if [num[i], num[left], num[right]] not in res:
                                res.append([num[i], num[left], num[right]])
                    else:
                        break
        return res

发表于 2021-09-04 14:05:41 回复(0)

Python3

长琴搞事

class Solution:
    def threeSum(self , num):
        res = set()
        def func(num, i, target):
            l, r = 0, len(num)-1
            while l < r and l != i and r != i:
                add = num[l] + num[r]
                if add == target:
                    res.add(tuple(sorted((num[l], num[r], num[i]))))
                    l += 1
                elif add > target: r -= 1
                else: l += 1
        num.sort()
        for i, v in enumerate(num):
            func(num, i, -v)
        return sorted(res)

发表于 2021-08-13 23:15:53 回复(0)