面试题 16.24 数对和

题目描述#

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

思路#

仍然是经典的两数之和，不过我们需要把满足条件的所有数对都枚举出来。遍历数组时：

用哈希表 cnt 统计左侧每个数字尚能匹配的次数；
枚举当前数字 x 时，先看 need = target - x 是否仍有可用配对；
若可用，就立刻把 [x, need] 追加到答案，并把 need 的剩余次数减一；否则把 x 的次数加一，等待后续元素匹配；
始终坚持“先匹配再入表”，即可保证每个元素至多使用一次。

时间复杂度 O(n)，空间复杂度 O(n)。

代码#

class Solution {
    public List<List<Integer>> pairSums(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            int count = cnt.getOrDefault(need, 0);
            if (count == 0) {
                cnt.merge(nums[i], 1, Integer::sum);
            } else {
                ans.add(Arrays.asList(nums[i], need));
                cnt.put(need, count - 1);
            }
        }
        return ans;
    }
}