正文
LeetCode 笔记27 Two Sum III - Data structure design
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
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.
这个解法很容易想到，但很容易超时。
基本来说有这样几个途径去解。
第一种，使用一个数组去存所有加入的元素，使用一个Set去存所有的和。在实现Find的时候，遍历数组，把能够得到的和都加到set中去。这样，find的时间复杂度是O(1)了，因为只需要判断value是否在集合里面，但是add就变成了O(n)。实践证明这是行不通的。
第二种，还是使用一个数组去存元素，但是每次加入的时候保持数组有序，这样虽然可以通过二分查找找到插入点，但是插入本身，由于是在数组中，复杂度就变成O(n)了。在实现Find的时候，使用TwoSum标准算法（用两个指针，一前一后遍历）。所以这个也没有好多少，还是会超时。
第三种，不要使用数组了。使用一个Search Tree来存放元素。这样在add的时候可以基本保证O(logn)。
Find怎么办呢？
其实也可以采用TwoSum的那个标准算法，但是需要在TreeNode里面存放一个pre和next指针，分别是排序后的，该节点的前一个和后一个元素。这样你远看是一颗树，近看是双向链表。
在二叉排序树中插入一个节点大家都会，要注意的是如何在插入的过程中，记录pre和next。其实只要是向右搜索，我们就给pre赋值，向左搜索就给next赋值就可以了。
哦，对了，还要在插入过程中注意update 双向链表的head和tail，这个也很容易，只要插入后发现pre是null，那么这个节点肯定是head嘛，next是null就是tail咯。
代码是这个。
public class TwoSumDS {
private TreeNode root;
private TreeNode head;
private TreeNode tail;
//private Set<Integer> seenSum = new HashSet<>();
public void add(int number) {
if (root == null) {
root = new TreeNode(number);
head = tail = root;
} else {
insertIntoTree(number);
}
}
public boolean find(int value) {
{
if (head != null && tail != null && head != tail) {
TreeNode p = head, q = tail;
while (p != q) {
int sum = p.val + q.val;
//seenSum.add(sum);
if (sum > value) {
q = q.pre;
} else if (sum < value) {
p = p.next;
} else {
return true;
}
}
}
}
return false;
}
private void insertIntoTree(int val) {
TreeNode p = root;
TreeNode pre = null;
TreeNode next = null;
while (true) {
//seenSum.add(val + p.val);
if (val > p.val) {
pre = p;
if (p.right != null) {
p = p.right;
} else {
p.right = new TreeNode(val);
insertInToChain(p.right, pre, next);
break;
}
} else {
next = p;
if (p.left != null) {
p = p.left;
} else {
p.left = new TreeNode(val);
insertInToChain(p.left, pre, next);
break;
}
}
}
}
private void insertInToChain(TreeNode n, TreeNode pre, TreeNode next) {
if (pre != null) {
pre.next = n;
} else {
head = n;
}
if (next != null) {
next.pre = n;
} else {
tail = n;
}
n.pre = pre;
n.next = next;
}
private static class TreeNode {
int val;
TreeNode right;
TreeNode left;
TreeNode pre;
TreeNode next;
TreeNode(int val) {
this.val = val;
}
}
public static void main(String[] args) {
TwoSumDS ts = new TwoSumDS();
ts.add(1);
ts.add(3);
ts.add(5);
System.out.println(ts.find(4));
System.out.println(ts.find(7));
}
}
注意到撸主注释的部分，有一个优化。就是在插入和搜索过程中，沿途找到的sum我们缓存起来，下次说不定可以用。Find的之前可以先在seenset里面看看。
不过这个优化导致了超时，所以就去掉了。看了一下Java doc，并没有gurantee HashSet的存放操作是O(1)的。
看来Java还没有很多人提交哟：>
