python - 检查多个条件以避免在 twoSum 解决方案中重复

Question

我为两个求和问题设计了三种解法

Given all arrays of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

一个是操作数据结构

class Solution1(): #Manipulate Data 
    def twoSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums_d = {}
        couples = []
        #O(n)
        for i in range(len(nums)):
            nums_d.setdefault(nums[i], []).append(i)

        for i in range(len(nums)):
            complement = target - nums[i]
            nums_d[nums[i]].pop(0) #remove the fixer
            result = nums_d.get(complement)#hash table to search 
            #if j is not Nne and j is not empty.
            if result: #if exits, it should be [j] 
                couples.append([nums[i], complement])
        return couples 

其次是多条件检查

class Solution2: #Double Pass Approach 
    def twoSum(self, nums, target) -> List[List[int]]:
        """
        :type nums: List[int]
        :type target: int
        """
        if len(nums) < 2:
            return []

        couples = []
        nums_d:dict = {}
        for i in range(len(nums)):
            #nums_d.setdefault(nums[i], []).append(i)
            nums_d[nums[i]] = i 

        for i in range(len(nums)):
            complement = target - nums[i]
            # nums_d[nums[i]].pop(0) #remove the fixer 
            if nums_d.get(complement) != None and nums_d.get(complement) != i: 
                couples.append([nums[i], complement])
        return couples

第三种只操作索引

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

        if len(nums) < 2:
            return []

        for i in range(len(nums)):
            complement = target - nums[i]
            logging.debug(f"complement: {complement}")
            logging.debug(f"Check: {nums_d.get(complement)}")

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

            logging.debug(f"nums_d: {nums_d}")
        return couples 

和我的测试用例

class TestCase(unittest.TestCase):
    # logging.debug("Class TestCase started.")
    """
    Test for 'twoSum.py'
    """
    def setUp(self):
        self.solution = Solution1()
        self.solution2 = Solution2()
        self.solution3 = Solution3()

    def test_two_sum3(self):
        #random is present
        target = 30
        nums = random.sample(range(20), k=20)
        print(f"\ntarget: {target} \nnums: {nums}")
        #Input no-replacement nums
        print('Solution Length:', len(self.solution.twoSum(nums, target)))
        print('result:', self.solution.twoSum(nums, target))
        print('Solution2 Length:', len(self.solution2.twoSum(nums, target)))
        print('result2:', self.solution2.twoSum(nums, target))
        print('Solution3 Length:', len(self.solution3.twoSum(nums, target)))
        print('result3:', self.solution3.twoSum(nums, target))


unittest.main()

得到结果

nums: [8, 0, 2, 15, 18, 5, 4, 14, 3, 12, 17, 19, 11, 10, 6, 16, 7, 13, 1, 9]
Solution Length: 4
result: [[18, 12], [14, 16], [17, 13], [19, 11]]
Solution2 Length: 8
result2: [[18, 12], [14, 16], [12, 18], [17, 13], [19, 11], [11, 19], [16, 14], [13, 17]]
Solution3 Length: 4
result3: [[12, 18], [11, 19], [16, 14], [13, 17]]
.
----------------------------------------------------------------------
Ran 3 tests in 0.001s

我是解决方案 2 的粉丝。

如何重写if nums_d.get(complement) != None and nums_d.get(complement) != i:
避免重复？

Answer 1

首先我想说，你的解决方案与两个和问题的陈述不完全匹配。

You may assume that each input would have exactly one solution, and you may not use the same element twice.

所以实际上，你不需要记录多个结果，只需找到并返回即可。

根据您的解决方案和测试用例，我假设您的场景适用于具有多个结果并忽略重复对的数据。

我想出两种方法来改善您的 Solution2 ，我也优化了你的代码，你可以对比学习评论:

1. 使用set和 sorted pair删除重复项:

class Solution4:
    def twoSum(self, nums, target) -> List[List[int]]:
        if len(nums) < 2:
            return []

        couples = set()
        nums_d = {v: i for i, v in enumerate(nums)}     # init by dict comprehension

        for i, v in enumerate(nums):    # enumerate is better here
            complement = target - v
            if nums_d.get(complement, i) != i:      # use sentinel, more concise
            # if complement in nums_d and nums_d[complement] != i:  # more understandable
                couples.add(tuple(sorted((nums[i], complement))))   # need immutable in set
        return list(map(list, couples))     # convert back to list

1. 只添加 complement >= v 的对(排序对)，比上面更有效。

注意:此解决方案不会通过输入中 [15, 15] 之类的情况，我只是假设没有这样的边缘情况， 因为您所有的 3 个原始解决方案也不会通过。

class Solution5:
    def twoSum(self, nums, target) -> List[List[int]]:
        if len(nums) < 2:
            return []

        couples = []
        nums_d = {v: i for i, v in enumerate(nums)}     # init by dict comprehension

        for i, v in enumerate(nums):    # enumerate is better here
            complement = target - v
            if complement >= v:
                if nums_d.get(complement, i) != i:      # use sentinel, more concise
                # if complement in nums_d and nums_d[complement] != i:  # more understandable
                    couples.append([v, complement])
        return couples

顺便说一句，我是Solution3的粉丝，它在遍历时更新索引，这是一种常用技术，使用较少的额外空间和一次遍历。

希望对您有所帮助，如果您还有其他问题，请发表评论。 :)