15. 3Sum

Leetcode

Given an array $S$ of $n$ integers, are there elements $a, b, c$ in $S$ such that $a + b + c = 0$? Find all unique triplets in the array which gives the sum of zero.

给出一个有$n$个整数的数组$S$，在$S$中找到三个整数$a, b, c$，找到所有使得$a + b + c = 0$的三元组。

For example, given array S = [-1, 0, 1, 2, -1, -4],

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

求一个列表中所有和为零的二元组的一种思路是先把列表排序，再用两个指针从两头向中间移动。如果前后两个数的和小于0，则左指针右移；如果和大于0，则右指针左移。求三元组时可以参考这种做法，第一个数a确定后，可以理解为求列表中和为-a的二元组。由于不要考虑重复的元组，遇到重复的数可以直接跳过。

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)

        # 如果为小于3个元素的列表
        if n < 3:
            return []

        # 排序
        nums = sorted(nums)
        print(nums)

        results = []
        i = 0
        while i < n-2:
            left = i+1
            right = len(nums)-1
            while left < right:
                val = nums[left] + nums[right] + nums[i]
                if val == 0:
                    results.append([nums[i], nums[left], nums[right]])
                    print([i, left , right], [nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    # Ignore repeat numbers
                    while (left < right) and  (nums[left] == nums[left-1]):
                        left += 1
                    while (left < right) and (nums[right] == nums[right+1]):
                        right -= 1

                elif val < 0:
                    left += 1
                else:
                    right -= 1

            i += 1
            # Ignore repeat numbers
            while i < n - 2 and nums[i] == nums[i - 1]:
                i += 1

        return results

Runtime: 976 ms