首页 > 代码库 > 3Sum

3Sum

2024-07-28 06:57:27   222人阅读

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)
 

分析：

这个问题是要从数列里面找到所有和是0的3个数。

对程序输出有两个限制，一是输出的三元组要按升序排列，二是输出的数列要去重，这在编码中会无法避免的导致检查和去重的代码实现。

用map来实现过滤的话，会很容易导致超时，但是在实际应用中，还是觉得用map自动处理比较好理解，而且代码稳定易读。

我写了一个函数，用来清楚表明3 Sum与2 Sum的区别。在这个twoSum里面实现了另外一种Two Sum的解法，略有差别是因为本题不需要返回索引，只要得到正确的数就可以了，所以省略了记录索引的步骤。

class Solution:    # @return a list of lists of length 3, [[val1,val2,val3]]    def threeSum(self, num):        values = []        num.sort()        for i, c in enumerate(num[:-2]):            if c > 0:                break            if i == 0 or num[i] > num[i - 1]:                values.extend(self.twoSum(num, c, i + 1))        return values    def twoSum(self, num, c, start):        ‘‘‘Another way for two sum problem‘‘‘        c = -c        values = []        end = len(num) - 1        while start < end:            if num[start] + num[end] == c:                values.append([-c, num[start], num[end]])                start += 1                end -= 1                while start < end and num[start] == num[start - 1]:                    start += 1                while start < end and num[end] == num[end + 1]:                    end -= 1            elif num[start] + num[end] < c:                start += 1            else:                end -= 1        return valuesif __name__ == ‘__main__‘:    s = Solution()    assert s.threeSum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]    assert s.threeSum([0, 0, 0]) == [[0, 0, 0]]    assert s.threeSum([-2, 0, 1, 1, 2]) == [[-2, 0, 2], [-2, 1, 1]]    assert s.threeSum([1, -1, -1, 0]) == [[-1, 0, 1]]    print ‘PASS‘

小结：

这个问题与TwoSum结合起来思考的话并不难，但是如果考虑4个数值的衍生情况，是否是O(n^3)的复杂度？

我附带贴上一个更为简洁的代码，但是无法过LeetCode的Online Judge，原因是为了代码的易读可靠超时了。LeetCode不支持set这个数据结构，否则

values = set()

更为简洁，避免了要给dict的value赋上一个值。

def threeSum2(self, num):        ‘‘‘This solution much clear but time out‘‘‘        values = {}        table = dict(zip(num, range(len(num))))        for i, c in enumerate(num[:-2]):            for j, b in enumerate(num[i + 1:], i + 1):                a = -c - b                if a in table and table[a] not in (i, j):                    values[tuple(sorted((a, b, c)))] = 1        return map(list, values.keys())

3Sum


联系
我们