这三个题目基本属于同一类型，这里我的解题思路是所谓的‘夹逼定理’。不同的题目运用该思路会有一点区别，总体上是大同小异。
先来看15题：
题目要求取出数列中可以加起来为0的三个数来组成序列并添加到新的序列中去。这个题目其实非常简单，和之前水桶装水的题目有些类似。这里只需要先绑定两端，中间的值动。
class Solution(object): def threeSum(self, nums): nums = sorted(nums) print(nums) out = [] for i in range(len(nums) - 2): if i>0 and nums[i] == nums[i-1]: continue f = i + 1 b = len(nums) - 1 while True: if f >= b: break if nums[i] + nums[f] + nums[b] < 0: f += 1 elif nums[i] + nums[f] + nums[b] > 0: b -= 1 else: out.append([nums[i], nums[f], nums[b]]) # if sorted([nums[i], nums[f], nums[b]]) not in out: # out.append(sorted([nums[i], nums[f], nums[b]])) f += 1 b -= 1 while f + 1 <= b and nums[f] == nums[f - 1]: f += 1 while b - 1 >= f and nums[b] == nums[b + 1]: b -= 1 return out
16.
class Solution: def threeSumClosest(self, nums, target): nums = sorted(nums) disminx = abs(nums[1] - nums[-1])+ abs(target) minx = sum(nums[:3]) for i in range(len(nums)): f, b = i + 1, len(nums) - 1 while f < b: num = nums[i] + nums[f] + nums[b] if num == target: return target elif num > target: b -= 1 minn = abs(num - target) if disminx > minn: disminx = minn minx = num else: f += 1 minn = abs(num - target) if disminx > minn: disminx = minn minx = num return minx
18
class Solution: def fourSum(self, nums, target): out = [] nums = sorted(nums) for i in range(len(nums)-3): if i > 0 and nums[i] == nums[i - 1]: continue for b in range(len(nums)-1,i+2,-1): if b < len(nums)-1 and nums[b] == nums[b+1]: continue f = i + 1 bf = b - 1 while True: Sum = nums[i] + nums[f] + nums[bf] + nums[b] #print(i, f, bf, b) #print([nums[i], nums[f], nums[bf], nums[b]]) if bf <= f: break elif Sum == target: print(‘==‘) out.append([nums[i],nums[f],nums[bf] , nums[b]]) bf-=1 while 0< bf < len(nums)-1 and nums[bf+1] == nums[bf]: bf -= 1 f+=1 while len(nums) -1> f >0 and nums[f] == nums[f-1]: f+=1 elif Sum > target: bf-=1 elif Sum < target: f += 1 return out
LeetCode算法题python解法：15. 3Sum 16. 3Sum Closest 18. 4Sum
原文：https://www.cnblogs.com/slarker/p/9657924.html