15. 3sum

先排序，然后最外层一个遍历，将当且的数字和余下部分的首尾的数字之和与0做比较，如果比0小, 将左指针向前一位，比0大将右指针向后一位，等于0则加到结果集里

O(n*n)

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 4 star        
        nums.sort()
        rs = set()
        for i in range(len(nums)-2):
            if i == 0 or nums[i] > nums[i-1]:  # 排除重复的数字
                left = i + 1
                right = len(nums) - 1
                while left < right:
                    total = nums[i] + nums[left] + nums[right]
                    if total < 0:
                        left += 1
                    elif total > 0:
                        right -= 1
                    else:
                        rs.add((nums[i], nums[left], nums[right]))
                        left += 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 threeSum(nums []int) [][]int {
	var ret [][]int
	sort.Ints(nums)
	length := len(nums)
	for index, _ := range nums {
		if index == 0 || nums[index] > nums[index-1] {   //去除重复
			left, right := index+1, length - 1
			for left < right {
				cur_sum := nums[index] + nums[left] + nums[right]
				if cur_sum > 0 {
					right -= 1  // 这几处的去除错误很巧妙，起初写错了很多次
					for left <= right && nums[right] == nums[right+1] {right -= 1}  // 去重
				} else if cur_sum < 0 {
					left += 1
					for left <= right && nums[left] == nums[left-1] {left += 1}  // 去重
				} else {
					ret = append(ret, []int {nums[index], nums[left], nums[right]})
					left += 1
					for left <= right && nums[left] == nums[left-1] {   // 去重
						left += 1}

				}
			}

		}

	}
	return ret

}