Yuan
0%

15. 3Sum

Posted on

https://leetcode.com/problems/3sum/editorial/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from collections import Counter

class Solution:
    def threeSum(self, A: List[int]) -> List[List[int]]:
        if not A:
            return []
        N=len(A)
        D={}
        S=set()

        A.sort()
        k=1
        B=[A[0]]
        for i in range(1,N):
            if A[i]==A[i-1]:
                k+=1
            else:
                k=1
            if k<=2 or k<=3 and A[i]==0:
                B.append(A[i])
        A=B
        N=len(A)
        for i,a in enumerate(A):
            D[a]=i
        
        for i in range(N):
            for j in range(i+1,N):
                C=-(A[i]+A[j]) # complement
                if C in D and D[C]!=i and D[C]!=j:
                    S.add(tuple(sorted([A[i],A[j],C])))
        ret=[]
        for l in S:
            ret.append(l)
        return ret