18. 4Sum

思路： 思路同3sum, 先排序，分别对前两个遍历，后两个从两边逼近

O(n^3)

Python:

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
class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        # 5 star,         
        nums.sort()
        rs = set()
        for i in range(len(nums) - 3):
            j = i + 1
            while j < len(nums) - 2:
                left = j + 1
                right = len(nums) - 1
                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total > target:
                        right -= 1
                    elif total < target:
                        left += 1
                    else:
                        rs.add((nums[i], nums[j], nums[left], nums[right]))
                        left += 1
                j += 1
        return list(rs)

Go:

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
func fourSum(nums []int, target int) [][]int {
	var ret [][]int
	length := len(nums)
	sort.Ints(nums)
	for first:=0; first < length-3; first++ {
		if first == 0 || nums[first] > nums[first-1] {  //防止第一个元素重复
			for second:=first+1; second < length-2;second++ {
				if second == first+1 || nums[second] > nums[second-1] {  //防止第二个元素重复
					left, right := second+1, length-1
					for left < right {
						curSum := nums[first] + nums[second] + nums[left] + nums[right]
						if curSum > target {
							right--
						} else if curSum < target {
							left++
						} else {
							ret = append(ret, []int{nums[first], nums[second], nums[left], + nums[right]})
							left++
							for left <= right && nums[left] == nums[left-1] {left++}  //防止第三个元素重复，前三项不重复，第四项肯定不会重复了
						}

				}
				}
			}

		}

	}
	return ret

}