TwoSum - Leetcode - 任何替代方式

Question

我正在学习如何编写代码逻辑并尝试使用这种逻辑并且它有效。

给定一个整数数组 nums 和一个整数目标，返回两个数字的索引，使它们相加等于目标。

您可以假设每个输入都有一个解决方案，并且您不能两次使用相同的元素。

您可以按任何顺序返回答案。

示例1：

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

示例2：

Input: nums = [3,2,4], target = 6
Output: [1,2]

示例3：

Input: nums = [3,3], target = 6
Output: [0,1]

我的代码：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        dt = {}

        for i,val in enumerate(nums):
            diff = target - val
            if diff not in dt:
                dt[val] = i
            else:
                return dt[diff],i

我想知道除了字典概念之外，他们还可以通过其他方式来实现它。

想以不同的方式探索更多的解决方案。

Answer 1

另一种方法可能是使用堆数据结构。如果暂时假设目标为 0，则可以通过输入值的 absolute 值对堆条目进行键控，然后从该堆中弹出元素并找到两个具有相同绝对值的连续弹出值，但与原始值相反，那么我们就找到了感兴趣的对。

要转换非零目标的问题，请将输入值映射到减去目标一半的值，或者 - 为了与整数值保持一致 - double。

这是一个实现：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        heap = [(abs(x := val * 2 - target), x, i) for i, val in enumerate(nums)]
        heapq.heapify(heap)
        prev = heapq.heappop(heap)
        curr = heapq.heappop(heap)
        while prev[1] != -curr[1]:
            prev = curr
            curr = heapq.heappop(heap)
        return [prev[2], curr[2]]