題目

給你一個(gè)由?n?個(gè)整數(shù)組成的數(shù)組?nums?，和一個(gè)目標(biāo)值?target?。請你找出并返回滿足下述全部條件且不重復(fù)的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個(gè)四元組元素一一對(duì)應(yīng)，則認(rèn)為兩個(gè)四元組重復(fù)）：

• 0 <= a, b, c, d?< n
• a、b、c?和?d?互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

解題

def fourSum(nums, target):nums.sort()  # 首先對(duì)數(shù)組進(jìn)行排序result = []  # 用于存儲(chǔ)結(jié)果的列表for i in range(len(nums) - 3):if i > 0 and nums[i] == nums[i - 1]:# 避免重復(fù)的四元組continuefor j in range(i + 1, len(nums) - 2):if j > i + 1 and nums[j] == nums[j - 1]:# 避免重復(fù)的四元組continueleft, right = j + 1, len(nums) - 1while left < right:total = nums[i] + nums[j] + nums[left] + nums[right]if total < target:left += 1elif total > target:right -= 1else:# 找到一個(gè)和為target的四元組result.append([nums[i], nums[j], nums[left], nums[right]])# 跳過重復(fù)的元素while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1# 移動(dòng)到下一個(gè)不同的元素left += 1right -= 1return result# 示例
nums = [1, 0, -1, 0, -2, 2]
target = 0
print(fourSum(nums, target))

[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]