面试题 16.24. 数对和

设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。

示例 1:

输入: nums = [5,6,5], target = 11
输出: [[5,6]]

示例 2:

输入: nums = [5,6,5,6], target = 11
输出: [[5,6],[5,6]]

提示：

• nums.length <= 100000

Python 解答：
1.双指针

class Solution:
    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        res = []
        i, j = 0, len(nums)-1
        while i < j:
            if nums[i] + nums[j] > target:
                j -= 1
            elif nums[i] + nums[j] < target:
                i += 1
            else:
                res.append([nums[i], nums[j]])
                j -= 1
                i += 1
        return res

2.哈希

class Solution:
    def pairSums(self, nums: List[int], target: int) -> List[List[int]]:
        adic = {}
        res = []
        for item in nums:
            if item not in adic.keys():
                adic[item] = 1
            else:
                adic[item] += 1
            k = target - item
            if k in adic.keys() and adic[k] > 0:
                if k != item:
                    res.append([item, k])
                    adic[k] -= 1
                    adic[item] -= 1
                elif adic[k] > 1:
                    res.append([item, k])
                    adic[k] -= 1
                    adic[item] -= 1
        return res