设计并实现一个 TwoSum 类。他需要支持以下操作:add 和 find 。

add -把这个数添加到内部的数据结构。 find -是否存在任意一对数字之和等于这个值

点此在线做题

样例 1:

add(1);add(3);add(5); find(4)//返回 true find(7)//返回 false 

[题解]

使用哈希表的方法是最快的。

• add 可以做到 O(1)
• find 可以做到 O(n)

public class TwoSum {     private Map<Integer, Integer> counter;          public TwoSum() {         counter = new HashMap<Integer, Integer>();     }      // Add the number to an internal data structure.     public void add(int number) {         counter.put(number, counter.getOrDefault(number, 0) + 1);     }      // Find if there exists any pair of numbers which sum is equal to the value.     public boolean find(int value) {         for (Integer num1 : counter.keySet()) {             int num2 = value - num1;             int desiredCount = num1 == num2 ? 2 : 1;             if (counter.getOrDefault(num2, 0) >= desiredCount) {                 return true;             }         }         return false;     } } // Your TwoSum object will be instantiated and called as such:// TwoSum twoSum = new TwoSum();// twoSum.add(number);// twoSum.find(value);  排序数组+双指针的算法会超时，但是大家可以看看是怎么写的，时间复杂度： - add O(n) - find O(n)  public class TwoSum {     public List<Integer> nums;     public TwoSum() {         nums = new ArrayList<Integer>();     }          public void add(int number) {         nums.add(number);         int index = nums.size() - 1;         while (index > 0 && nums.get(index - 1) > nums.get(index)) {             int temp = nums.get(index);             nums.set(index, nums.get(index - 1));             nums.set(index - 1, temp);             index--;         }     }      public boolean find(int value) {         int left = 0, right = nums.size() - 1;         while (left < right) {             int twoSum = nums.get(left) + nums.get(right);             if (twoSum < value) {                 left++;             } else if (twoSum > value) {                 right--;             } else {                 return true;             }         }         return false;     } } 

查看更多题解

大佬有話說 (0)