Design Hash Table

Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value.

相似题目
简单 Two Sum
Two Sum IV - Input is a BST
中等 Unique Word Abbreviation

双指针法

先给出双指针在有序列表中找到两数之和的算法。

  • 初始化两个指针 low 和 high 分别指向列表的头尾。
  • 从两个方向同时进行迭代，要么找到两数之和的解，要么两个指针相遇。
  • 在每个步骤中，我们将根据不同的条件移动指针：
    • 如果当前指针指向元素的和小于目标值，则应该增加总和来满足目标值，即将 low 指针向前移动获得更大的值。
    • 如果当前指针指向元素的和大于目标值，则应该减少总和来满足目标值，即将 high 向 low 靠近来减少总和。
    • 如果当前指针指向元素的和等于目标值，则直接返回结果。
    • 如果两个指针相交，说明当前列表不存在组合成目标值的两个数

我们会发现， add(number) 函数将被频繁调用，而 find(value) 将不被那么频繁调用。
这样的使用模式下，意味着我们应该减少 add(number) 函数的时间消耗，因而我们是在 find(value) 对列表进行排序，而不是在 add(number) 。

  1. class TwoSum {
  3.     private List<Integer> nums;
  4.     private boolean isSorted;
  6.     /** Initialize your data structure here. */
  7.     public TwoSum() {
  8.         this.nums = new ArrayList<>();
  9.         this.isSorted = false;
  10.     }
  12.     /** Add the number to an internal data structure.. */
  13.     public void add(int number) {
  14.         this.nums.add(number);
  15.         this.isSorted = false;
  16.     }
  18.     /** Find if there exists any pair of numbers which sum is equal to the value. */
  19.     public boolean find(int value) {
  20.         if (!this.isSorted) {
  21.             Collections.sort(this.nums);
  22.         }
  24.         int low = 0, high = this.nums.size() - 1;
  25.         while (low < high) {
  26.             int sum = this.nums.get(low) + this.nums.get(high);
  27.             if (sum == value) {
  28.                 return true;
  29.             } else if (sum < value) {
  30.                 low++;
  31.             } else {
  32.                 high--;
  33.             }
  34.         }
  35.         return false;
  36.     }
  37. }
  39. /**
  40.  * Your TwoSum object will be instantiated and called as such:
  41.  * TwoSum obj = new TwoSum();
  42.  * obj.add(number);
  43.  * boolean param_2 = obj.find(value);
  44.  */

哈希表法

和我自己的做法差不多，用哈希表实现快速查找和插入。只是 key 代表数字，value 代表出现次数。

  1. class TwoSum {
  3.     HashMap<Integer, Integer> numCount;
  5.     /** Initialize your data structure here. */
  6.     public TwoSum() {
  7.         this.numCount = new HashMap<>();
  8.     }
  10.     /** Add the number to an internal data structure.. */
  11.     public void add(int number) {
  12.         if (numCount.containsKey(number)) {
  13.             numCount.replace(number, this.numCount.get(number) + 1);
  14.         } else {
  15.             numCount.put(number, 1);
  16.         }
  17.     }
  19.     /** Find if there exists any pair of numbers which sum is equal to the value. */
  20.     public boolean find(int value) {
  21.         for (Map.Entry<Integer,Integer> entry : this.numCount.entrySet()) {
  22.             int pair = value - entry.getKey();
  23.             if (pair == entry.getKey()) {
  24.                 if (entry.getValue() > 1) {
  25.                     return true;
  26.                 }
  27.             } else {
  28.                 if (this.numCount.containsKey(pair)) {
  29.                     return true;
  30.                 }
  31.             }
  32.         }
  33.         return false;
  34.     }
  35. }
  37. /**
  38.  * Your TwoSum object will be instantiated and called as such:
  39.  * TwoSum obj = new TwoSum();
  40.  * obj.add(number);
  41.  * boolean param_2 = obj.find(value);
  42.  */

自己的解法

使用哈希表，key代表存储的数字，value代表该数字是否重复

  1. class TwoSum {
  2.     // key代表存储的数字，value代表该数字是否重复
  3.     Map<Integer, Boolean> map;
  5.     /** Initialize your data structure here. */
  6.     public TwoSum() {
  7.         map = new HashMap<>();
  8.     }
  10.     /** Add the number to an internal data structure.. */
  11.     public void add(int number) {
  12.         if (!map.containsKey(number)) {
  13.             // 代表没有重复
  14.             map.put(number, false);
  15.         } else {
  16.             // 代表有重复
  17.             map.put(number, true);
  18.         }
  19.     }
  21.     /** Find if there exists any pair of numbers which sum is equal to the value. */
  22.     public boolean find(int value) {
  23.         for (Map.Entry<Integer, Boolean> entry : map.entrySet()) {
  24.             int key = entry.getKey();
  25.             int pair = value - key;
  26.             if (pair != key && map.containsKey(pair)) {
  27.                 // 如果pair和key不相同，检查map中是否有pair
  28.                 return true;
  29.             } else if (pair == key && map.get(key) == true){
  30.                 // 如果pair和key相同且,检查key是否有重复值
  31.                 return true;
  32.             }
  33.         }
  34.         return false;
  35.     }
  36. }
  38. /**
  39.  * Your TwoSum object will be instantiated and called as such:
  40.  * TwoSum obj = new TwoSum();
  41.  * obj.add(number);
  42.  * boolean param_2 = obj.find(value);
  43.  */