难度: Medium
设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
示例 1:
输入: nums = [5,6,5], target = 11 输出: [[5,6]]
示例 2:
输入: nums = [5,6,5,6], target = 11 输出: [[5,6],[5,6]]
提示：
nums.length <= 100000-10^5 <= nums[i], target <= 10^5
Submission
运行时间: 82 ms
内存: 36.1 MB
class Solution:
def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
d={}
res=[]
for n in nums:
if target-n in d and d[target-n]>=1:
res.append([target-n,n])
d[target-n]-=1
else:
d[n]=d.get(n,0)+1
return res
Explain
该题解采用了哈希表的方法来解决问题。首先，遍历数组中的每个元素，对于当前元素n，检查target-n是否已经在哈希表中，如果存在，说明找到了一对和为target的数对，将这对数对添加到结果列表中，并将哈希表中对应的计数减一。如果不存在，将当前元素n添加到哈希表中，计数加一。这样可以确保每个数只能属于一个数对。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
d = {} # 哈希表用于存储元素及其出现次数
res = [] # 结果列表
for n in nums: # 遍历数组中的每个元素
if target - n in d and d[target - n] >= 1: # 如果找到配对元素
res.append([target - n, n]) # 添加到结果列表
d[target - n] -= 1 # 减少配对元素的计数
else:
d[n] = d.get(n, 0) + 1 # 否则，增加当前元素的计数
return res # 返回结果列表
Explore
在哈希表中，元素n的处理是通过记录每个元素的出现次数来管理的。如果数组中存在多个相同的n，则每次遍历到n时，都会在哈希表中增加n的计数（使用d[n] = d.get(n, 0) + 1）。这样，哈希表中的值（d[n]）就代表元素n在数组中剩余的可用次数。当需要配对时，检查target-n是否存在，并且其计数大于0，如果是，则可以形成一对，并相应地减少其在哈希表中的计数。
减少哈希表中的计数是必要的步骤，以确保每个数字只被使用一次。然而，这种方法可能导致潜在的问题，如在并发环境下，如果哈希表的更新（减少计数）没有正确同步，可能会出现竞态条件，导致计数不准确。此外，如果代码中减少计数的逻辑不正确（例如，未检查计数是否大于0就减少），可能会导致计数变为负数，从而引发错误或不一致的行为。
题解中通过在哈希表中记录每个元素的计数来确保每个数只能被用一次。对于每个遍历到的元素n，首先检查target-n是否已存在于哈希表中，并且其计数大于0。如果条件满足，说明可以形成一对，将该对添加到结果中，并将target-n的计数减一。这样就确保了一旦一个数字被用作配对，其在哈希表中的可用次数就会相应减少。如果target-n不在哈希表中或计数为0，则将n的计数增加，等待未来的配对。这种方法确保了每个数字最多只被使用一次来形成数对。