力扣 170. 两数之和 III - 数据布局设计 two-sum III

数组系列

力扣数据布局之数组-00-概览
力扣.53 最大子数组和 maximum-subarray
力扣.128 最长一连序列 longest-consecutive-sequence
力扣.1 两数之和 N 种解法 two-sum
力扣.167 两数之和 II two-sum-ii
力扣.170 两数之和 III two-sum-iii
力扣.653 两数之和 IV two-sum-IV
力扣.015 三数之和 three-sum
力扣.016 最靠近的三数之和 three-sum-closest
力扣.259 较小的三数之和 three-sum-smaller
题目

题目描述
设计一个接收整数流的数据布局，该数据布局支持查抄是否存在两数之和即是特定值。
实现 TwoSum 类：
TwoSum() 使用空数组初始化 TwoSum 对象
void add(int number) 向数据布局添加一个数 number
boolean find(int value) 寻找数据布局中是否存在一对整数，使得两数之和与给定的值相当。如果存在，返回 true ；否则，返回 false 。
示例：

1. 输入：
2. ["TwoSum", "add", "add", "add", "find", "find"]
3. [[], [1], [3], [5], [4], [7]]
4. 输出：
5. [null, null, null, null, true, false]

复制代码

解释：

1. TwoSum twoSum = new TwoSum();
2. twoSum.add(1);   // [] --> [1]
3. twoSum.add(3);   // [1] --> [1,3]
4. twoSum.add(5);   // [1,3] --> [1,3,5]
5. twoSum.find(4);  // 1 + 3 = 4，返回 true
6. twoSum.find(7);  // 没有两个整数加起来等于 7 ，返回 false

复制代码

思路

这一题和 001 第一题是一样的，可以参考 T001 和 T167 的解法，这里把这一题单独拿出来只是为了学习的系统性。
所以不做过多的展开。
区别

这一题另有一个核心的区别是数据会不停变革，所以数组的排序会打扣头。
当然也可以调整为对应的插入排序等算法。
常见算法

• 暴力
  

2）借助 Hash

• 排序+二分
  

4）双指针==》针对有序数组
在这个场景里面，最简单好用的应该是 HashMap 的方式
实现

1. class TwoSum {
2.     private Map<Integer, Integer> cnt = new HashMap<>();
4.     public TwoSum() {
5.     }
7.     public void add(int number) {
8.         cnt.merge(number, 1, Integer::sum);
9.     }
11.     public boolean find(int value) {
12.         for (var e : cnt.entrySet()) {
13.             int x = e.getKey(), v = e.getValue();
14.             int y = value - x;
15.             if (cnt.containsKey(y) && (x != y || v > 1)) {
16.                 return true;
17.             }
18.         }
19.         return false;
20.     }
21. }
23. /**
24. * Your TwoSum object will be instantiated and called as such:
25. * TwoSum obj = new TwoSum();
26. * obj.add(number);
27. * boolean param_2 = obj.find(value);
28. */

复制代码

小结

我们把握了核心的思路，不同的场景只需要举行相关的调整就行。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。