如何使用hashmap来解决这个问题？
如何使用hashmap来解决这个问题？
提问于 2015-10-18 17:32:10
假设为您提供了以下值的列表：
[1,4,5,7,8,9]给出了k=4，其中k是两个数组元素之间的区别。您如何发现k出现了多少次？例如，在这个列表中，k出现了3次[(5-1),(8-4),(9-5)]
我能够用两个for循环来解决这个问题，但这需要O(n^2)时间。我听说这可以用hashmap解决，但我不知道如何实现它？
任何想法都将不胜感激！
回答 5
Stack Overflow用户
回答已采纳
发布于 2015-10-18 17:38:06
其思想是在输入数组(numbers)中存储k和每个值之间的所有可能的差异。然后计算输入数组中符合差异的值数。
这将起作用：
public class Solution {
public int twoSum(int[] numbers, int k) {
if (numbers == null) {
return null;
}
int count = 0;
HashMap<Integer, Integer> difference = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
difference.put(k - numbers[i], i);
}
for (int i = 0; i < numbers.length; i++) {
int cur = -numbers[i];
if (difference.containsKey(cur) && difference.get(cur) != i) {
count++;
}
}
return count;
}
}捕获的方法是设置difference.get(cur) != i条件(其中i是索引cur)，以避免使用k = 0的情况，并且每个值将与自身形成一对。
Stack Overflow用户
发布于 2015-10-18 17:42:53
使用HashSet (在内部使用HashMap)，我们可以假设它的contains方法接近O(1)，所以您可以
- 用所有的元素填充这样的集合
- 迭代元素并计算
+4和-4差异的值 - 检查集合中是否存在这些值。
- 将结果除以2，因为对
1,5和5,1将得到真结果，这实际上是一对。
作为shown by Óscar López，您可以通过只计算+4和-4中的一个并跳过最后一步来改进它
Stack Overflow用户
发布于 2015-10-18 17:43:17
实际上，可以使用一个Set来解决这个问题:我们必须找到这个集合是否包含另一个元素，其结果与k中当前的结果不同。尝试以下解决方案，它的工作假设输入中至少有两个元素没有重复项，并且不会像我们使用HashMap来解决这个问题那样浪费空间用于不需要的值：
int k = 4;
int howMany = 0;
Set<Integer> set = new HashSet<>(Arrays.asList(1, 4, 5, 7, 8, 9));
System.out.printf("k = %d%n", k);
for (Integer n : set) {
if (set.contains(n - k)) {
howMany++;
System.out.printf("(%d - %d) = k%n", n, n - k);
}
}
System.out.printf("k appears %d times%n", howMany);上述结果的结果如下：
k = 4
(5 - 1) = k
(8 - 4) = k
(9 - 5) = k
k appears 3 times页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33201032
复制相关文章
相似问题
腾讯云开发者
