3sum

题目描述

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.

Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

解题方法

这里的思想主要是，取出一个元素i，然后再用two sum的方法求其他两个，它们的sum为target - i

遇到题目没有思路的时候都可以考虑先sort一下~

注意点

• 不能有重复的set, 所以都要将数组sort一下，方便在code中跳过重复的数
• two sum可以用hashmap, 也可以用two pointer的方法

时间复杂度O(nlogn + n * n) = O(n^2)

Solution

hashmap的方法

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        numbers = nums
        if len(numbers) < 3:
            return []
        numbers.sort()
        results = []
        for idx, num in enumerate(numbers):
            if idx != 0 and num == numbers[idx-1]:
                #跳过重复元素
                continue
            target = 0 - num
            #only start with afterward elements
            twoSumResults = self.twoSum(numbers[idx+1:], target)
            if twoSumResults:
               for comb in twoSumResults:
                    #index should start from idx + 1
                    result = [numbers[idx], numbers[comb[0] + idx + 1], numbers[comb[1] + idx + 1]]
                    result.sort()
                    results.append(result)
        return results

    def twoSum(self, numbers, target):
        # need to find all combinations now
        results = []
        found = False
        for idx, num in enumerate(numbers):
            dic[num] = idx
        for idx, num in enumerate(numbers):
            #跳过重复元素
            if idx != 0 and num == numbers[idx-1]:
                continue
            t = target - num
            if t in dic and dic[t] > idx:
                #该元素在idx的后面
                found = True
                results.append([idx, dic[t]])

        if not found:
            return None
        return results

two pointer的方法

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        numbers = nums
        if len(numbers) < 3:
            return []
        numbers.sort()
        results = []
        for idx, num in enumerate(numbers):
            if idx != 0 and num == numbers[idx-1]:
                continue
            target = 0 - num
            #only start with afterward elements
            twoSumResults = self.twoSum(numbers[idx+1:], target)
            if twoSumResults:
               for comb in twoSumResults:
                    #index should start from idx + 1
                    result = [numbers[idx], numbers[comb[0] + idx + 1], numbers[comb[1] + idx + 1]]
                    result.sort()
                    results.append(result)
        return results

    def twoSum(self, numbers, target):
        # need to find all combinations now
        dic = {}
        index1 = None
        index2 = None
        results = []
        found = False
        start, end = 0, len(numbers) - 1
        while start < end:
            if start != 0 and numbers[start] == numbers[start-1]:
                start += 1
            elif end != len(numbers) - 1 and numbers[end] == numbers[end+1]:
                end -= 1
            else:
                curSum = numbers[start] + numbers[end]
                if curSum == target:
                    found = True
                    results.append([start, end])
                    start += 1
                    end -= 1
                elif curSum < target:
                    start += 1
                else:
                    end -= 1


        if not found:
            return None
        return results