https://leetcode-cn.com/problems/4sum/submissions/
思路:n个数之和,n-2重for循环 + 双指针
python
class Solution(object):
def fourSum(self, nums, target):
if len(nums) < 4:
return []
res = []
nums.sort()
for i in range(len(nums) - 3): # 第一个元素只需要遍历 0...n-3 就行
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, len(nums) - 2):
if j > i + 1 and nums[j] == nums[j-1]:
continue
new_tgt = target - nums[i] - nums[j]
left, right = j + 1, len(nums) - 1
while left < right:
if nums[left] + nums[right] == new_tgt:
res.append( [nums[i], nums[j], nums[left], nums[right]] )
left, right = left + 1, right - 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif nums[left] + nums[right] < new_tgt:
left += 1
else:
right -= 1
return res