⭐ 题目日期：

快手 - 2024/9/14

🌳 题目描述：

一个数组 {1，2， 3， 4， 3， 4， 9}，target = 9，求出两个数乘积为 target 的组合, result = [[1, 9], [3, 3]]。结果满足：

1. 无需返回重复的组合
2. 可以按任意组合顺序返回，如 [1, 9] 和 [9, 1] 视为相同的组合

示例 1：
输入：inputs = [1, 2, 3, 4, 3, 4, 9, 9]，target = 9
输出：result = [[1, 9], [3, 3]]

🕵🏽 面试评估：

这道题主要考察哈希表的理解与运用，与经典面试算法题两数之和解法相似。

🧗难度系数：

⭐️ ⭐️

📝思路分析：

需要寻找出数组中所有乘积等于目标值的数对，且需要不重复，我们可以使用哈希表 map 来跟踪已访问的数字和确认数对是否已添加。

对每个数字，我们首先判断它是否是目标数的因子，如果不是，直接跳过，进行下一个数的判断。

如果是即计算出它相应的补数（即另一个因子）。随后检查 map 中是否已存在此补数，如果不存在，那么将其加入 map 集合中，进行下一个数的判断。

如果存在，那么说明已经找到有相对应的数对，如果 map 中 <key, value> 的 value 为 null，证明 result 集合中没有该数对，那么就将其添加到 result 中，并在 <key, value> 和 <value, key> 都加入到 map 中，避免后续重复添加相同的组合。

重复以上步骤，遍历完数组，最后将 result 返回。

以案例为例，图解如图所示。

💻代码：

Java

public List<List<Integer>> twoProduct(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return result;
    }

    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        if (num != 0 && target % num == 0) {
            if (map.containsKey(target / num)) {
                if (map.getOrDefault(target / num, null) == null) {
                    result.add(List.of(target / num, num));
                    map.put(target / num, num);
                    map.put(num, target / num);
                }
            } else {
                map.put(num, null);
            }
        }
    }

    return result;
}

Python

def two_product(nums, target):
    result = []
    if not nums or len(nums) == 0:
        return result

    map_dict = {}
    for num in nums:
        if num != 0 and target % num == 0:
            complement = target // num
            if complement in map_dict:
                if map_dict.get(complement) is None:
                    result.append([complement, num])
                    map_dict[complement] = num
                    map_dict[num] = complement
            else:
                map_dict[num] = None

    return result

🚵🏻复杂度分析：

时间复杂度：O(n)， n 为数组的长度，数组中的所有元素遍历一遍，并且哈希表的查询，添加操作平均时间复杂度均为 O(1)。

空间复杂度：O(n)，哈希表最多存储 n 对 <key, value> pair; result list 最多存储数组中所有的数。