python - twoSum查找所有可能的唯一对

我有这样的问题
给定n个整数的数组nums，在nums中是否有元素a，b使得a+b=10？找出数组中给出目标和的所有唯一对。
注：
解决方案集不能包含重复的对。
例子：

Given nums = [4, 7, 6, 3, 5], target = 10

because   4+ 6= 7+ 3   = 10
return  [[4, 6], [7,3]]

我的解决方案：

class SolutionAll: #Single Pass Approach
    def twoSum(self, nums, target) -> List[List[int]]:
        """
        :type nums: List[int]
        :type target: int
        """
        nums.sort()
        nums_d:dict = {}
        couples = []

        if len(nums) < 2:
            return []

        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]: continue #skip the duplicates

            complement = target - nums[i]

            if nums_d.get(complement) != None:
                couples.append([nums[i], complement])
            nums_d[nums[i]] = i
        return couples

测试用例结果：

target: 9
nums: [4, 7, 6, 3, 5]
DEBUG　complement: 6
DEBUG　nums_d: {3: 0}
DEBUG　couples: []
DEBUG　complement: 5
DEBUG　nums_d: {3: 0, 4: 1}
DEBUG　couples: []
DEBUG　complement: 4
DEBUG　nums_d: {3: 0, 4: 1, 5: 2}
DEBUG　couples: [[5, 4]]
DEBUG　complement: 3
DEBUG　nums_d: {3: 0, 4: 1, 5: 2, 6: 3}
DEBUG　couples: [[5, 4], [6, 3]]
DEBUG　complement: 2
DEBUG　nums_d: {3: 0, 4: 1, 5: 2, 6: 3, 7: 4}
DEBUG　couples: [[5, 4], [6, 3]]
result: [[5, 4], [6, 3]]
.
target: 2
nums: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
DEBUG　complement: 2
DEBUG　nums_d: {0: 0}
DEBUG　couples: []
DEBUG　complement: 1
DEBUG　nums_d: {0: 0, 1: 9}
DEBUG　couples: []
result: []

该解决方案可用于[4、7、6、3、5]，但失败于[0、0、0、0、0、0、0、0、0、1、1、1、1、1、1、1]
我试图删除重复项，但得到了意外的结果。
用这种一次解决办法怎么能解决这个问题呢？

最佳答案

代码的问题在于它跳过了重复的数字，而不是重复的对。因为

if i > 0 and nums[i] == nums[i-1]: continue #skip the duplicates

您的代码从不尝试对1 + 1 = 2求和。
这里有一个工作解决方案：O(n)复杂性：

from collections import Counter

def two_sum(nums, target):
    nums = Counter(nums)  # count how many times each number occurs

    for num in list(nums):  # iterate over a copy because we'll delete elements
        complement = target - num

        if complement not in nums:
            continue

        # if the number is its own complement, check if it
        # occurred at least twice in the input
        if num == complement and nums[num] < 2:
            continue

        yield (num, complement)

        # delete the number from the dict so that we won't
        # output any duplicate pairs
        del nums[num]

>>> list(two_sum([4, 7, 6, 3, 5], 10))
[(4, 6), (7, 3)]
>>> list(two_sum([0, 0, 0, 1, 1, 1], 2))
[(1, 1)]

另见：
collections.Counter
What does the "yield" keyword do?