Leetcode/problem18.py at master · Yuchen112211/Leetcode · GitHub

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
'''

18. 4Sum
Medium

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]


Solution:
With every element, we do the three sum algorithm.

'''

class Solution:
	def fourSum(self, nums, target):
		res = []
		nums.sort()
		for i in range(len(nums)):
			if i == 0 or nums[i] > nums[i-1]:#Without the =, we can skip the duplicate.
				diff = target - nums[i]
				threeSums = self.threeSum(nums[i+1:], diff)
				for threeSum in threeSums:
					res.append([nums[i]] + threeSum)
		return res


	def threeSum(self, nums, target):
		res = []
		if len(nums) < 3: return res

		for i in range(len(nums) - 2):
			if i > 0 and nums[i] == nums[i-1]: continue
			l, r = i + 1, len(nums) - 1
			while l < r :
				s = nums[i] + nums[l] + nums[r]
				if s == target:
					res.append([nums[i] ,nums[l] ,nums[r]])
					l += 1; r -= 1
					while l < r and nums[l] == nums[l - 1]: l += 1
					while l < r and nums[r] == nums[r + 1]: r -= 1
				elif s < target :
					l += 1
				else:
					r -= 1
		return res

if __name__ == '__main__':
	nums = [0,1,5,0,1,5,5,-4]
	s = Solution()
	print s.fourSum(nums,11)