给定一个包含 n 个整数的列表，如何找到其中总和为 k 的不同元素对的数量？

Question

如何使用哈希图来解决这个问题？我对当前的解决方案有点挣扎。

完整问题：

我不确定为什么结果总是返回 0，我在这里错过了什么？

int numberOfWays(int[] arr, int k) {
// Write your code here
HashMap<Integer, Integer> sums = new HashMap<Integer,Integer>();
int results = 0;
for (int i = 0; i < arr.length; i++) {
  if (!sums.containsKey(arr[i])){
    sums.put(arr[i], k-arr[i]);
  }
  if (Arrays.asList(arr).contains(sums.get(arr[i]).intValue())) {
    results++;
  }
}
return results;

Answer 1

在示例代码中，请考虑迭代

arr

次数。另请参阅：大 O。

如何使用哈希图来解决这个问题？

这是代码/伪代码步骤的组合：

使用 TreeMap 所以它是自然排序的

// map key will be value from `arr`
// map value is how many times the value occurs in `arr`
var elements = new TreeMap<Integer, Integer>();

预处理步骤：

for each element in `arr`
    add to `elements` map if it does not already exist
    if does alreday existincrement element value if it already exists

加工步骤：

// using TreeMap makes it naturally ordered so can reduce the number of elements to check
for each element in elements up to (k / 2)
   if element key - k is in elements
     then result += elements.get(element.key - k).value

       
return result;