理论基础
哈希表
三数之和
题目描述
三数之和
示例
给定 [-1,0,1,2,-1,-4], target=0
解题思路
暴力解法 O (N^3)
a+b+c=0 O(N^2)
双指针
Python 解法
# a+b+c=0 def threeSum(self, nums): if len(nums) < 3: return [] nums.sort() res = set() for i, v in enumerate(nums[:-2]): if i >= 1 and v == nums[i-1]: continue d = {} for x in nums[i+1:]: if x not in d: d[-v-x] = 1 else: res.add((v, -v-x, x)) return map(list, res) # 双指针 def threeSum(self, nums): res = [] nums.sort() for i in xrange(len(nums)-2): if i > 0 and nums[i] == nums[i-1]: cintinue l, r = i+1, len(nums)-1 while l < r: s = nums[i] + nums[l] + nums[r] if s < 0: l += 1 elif s > 0: r -= 1 else: res.append((nums[i], nums[l], nums[r])) # 判重处理 while l < r and nums[l] == nums[l+1]: l += 1 while l < r and nums[r] == nums[r-1]: r -= 1 l += 1; r -= 1 return res
© 著作权归作者所有
举报
发表评论
0/200