LeetCode 3Sum

LeetCode解題之3Sum

原題

找出一個列表中所有和為零的三元組。要求求出的三元組中沒有重復。

注意點：

例子：

輸入: nums=[-1, 0, 1, 2, -1, -4]
輸出: [[-1, -1, 2], [-1, 0, 1]]

解題思路

求一個列表中所有和為零的二元組的一種思路是先把列表排序，再用兩個指針從兩頭向中間移動。如果前後兩個數的和小於0，則左指針右移；如果和大於0，則右指針左移。求三元組時可以參考這種做法，第一個數a確定後，可以理解為求列表中和為-a的二元組。由於不要考慮重復的元組，遇到重復的數可以直接跳過。

AC源碼

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # Sorted array can save a lot of time
        nums.sort()
        result = []
        i = 0
        while i < len(nums) - 2:
            j = i + 1
            k = len(nums) - 1
            while j < k:
                l = [nums[i], nums[j], nums[k]]
                if sum(l) == 0:
                    result.append(l)
                    j += 1
                    k -= 1
                    # Ignore repeat numbers
                    while j < k and nums[j] == nums[j - 1]:
                        j += 1
                    while j < k and nums[k] == nums[k + 1]:
                        k -= 1
                elif sum(l) > 0:
                    k -= 1
                else:
                    j += 1
            i += 1
            # Ignore repeat numbers
            while i < len(nums) - 2 and nums[i] == nums[i - 1]:
                i += 1
        return result


if __name__ == "__main__":
    assert Solution().threeSum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]

歡迎查看我的Github來獲得相關源碼。