首页 > 代码库 > 3Sum
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)
分析:
这个问题是要从数列里面找到所有和是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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。