python - twoSum 找出所有可能的独特情侣

问题描述

我有这样的问题

给定一个包含 n 个整数的数组nums，是否存在满足a + b = 10 的元素a和b ？在给出目标总和的数组中找到所有唯一的对。nums

笔记：

解决方案集不得包含重复的对。

例子：
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]

我试图删除重复项，但得到了意想不到的结果。

如何用这个 Pass 解决方案解决问题？

标签： pythonpython-3.xalgorithm

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

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)]

也可以看看：

python - twoSum 找出所有可能的独特情侣

问题描述

解决方案

推荐阅读