FilesExpand file tree

 main

/

4Sum.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

44 lines (37 loc) · 1.3 KB

 main

/

4Sum.py

Copy path

Top

File metadata and controls

• Code
• Blame

44 lines (37 loc) · 1.3 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

35

36

37

38

39

40

41

42

43

44

# https://leetcode.com/problems/4sum/

class Solution(object):

def fourSum(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: List[List[int]]

"""

a=[]

nums=sorted(nums)

i=0

while i < len(nums):

j=i+1

while j<len(nums):

tgt=target-nums[i]-nums[j]

fr=j+1

bk=len(nums)-1

while fr<bk:

if nums[fr]+nums[bk]<tgt:

fr+=1

elif nums[fr]+nums[bk]>tgt:

bk-=1

else:

tr=[nums[i],nums[j],nums[fr],nums[bk]]

if nums[fr]+nums[bk]==tgt:

a.append(tr)

while fr<bk and nums[fr]==tr[2]:

fr+=1

while fr<bk and nums[bk]==tr[3]:

bk-=1

while j<len(nums)-1 and nums[j]==nums[j+1]:

j+=1

j+=1

while i<len(nums)-1 and nums[i]==nums[i+1]:

i+=1

i+=1

return a