Massive Algorithms: leetcode 170: Two Sum III

leetcode 170: Two Sum III - Data structure design

leetcode 170: Two Sum III - Data structure design - 西施豆腐渣 - 博客频道 - CSDN.NET
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.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

X. https://blog.csdn.net/magicbean2/article/details/72910861
2、find优先：
TwoSum() {

}

/** Add the number to an internal data structure.. */
void add(int number) {
for (int i = 0; i < nums.size(); ++i) {
sums.insert(nums[i] + number);
}
nums.push_back(number);
}

/** Find if there exists any pair of numbers which sum is equal to the value. */
bool find(int value) {
return sums.find(value) != sums.end();
}
private:
vector<int> nums;
unordered_set<int> sums;

https://leetcode.com/discuss/19515/my-solutions-java-and-python-time-for-add-time-for-find-space
O(1) time for add, O(n) time for find, O(n) space
I use HashMap to store times of number be added. When find be called, we iterate the keys of HashMap, then find another number minus by value. Then combine the detections together.
http://buttercola.blogspot.com/2015/08/leetcode-two-sum-iii-data-structure.html

    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();

 public void add(int number) {

     if (map.containsKey(number)) {

         int val = map.get(number) + 1;

         map.put(number, val);

     } else {

         map.put(number, 1);

}

}

 public boolean find(int value) {

     if (map.isEmpty()) {

         return false;

}

     Iterator it = map.entrySet().iterator();

     // Itearte over the set

     while (it.hasNext()) {

         Map.Entry pair = (Map.Entry) it.next();

         int firstKey =  (int) pair.getKey();

         int firstValue = (int) pair.getValue();

         int secondKey = value - firstKey;

         // 0 + 0 = 0

         if (firstKey == secondKey && firstValue >= 2) {

             return true;

         }  else if (firstKey != secondKey && map.containsKey(secondKey)) {

             return true;

}

}

     return false;

}

Clean code: http://yuanhsh.iteye.com/blog/2186428

Map<Integer, Integer> dict = new HashMap<Integer, Integer>();
public void add(int number) {
if (dict.containsKey(number)) {
dict.put(number, dict.get(number) + 1);
} else {
dict.put(number, 1);
}
}
public boolean find(int value) {
for (Integer key : dict.keySet()) {
if (value - key == key) {
if (dict.get(key) >= 2) {
return true;
}
} else if (dict.containsKey(value - key)) {
return true;
}
}
return false;
}

public class TwoSum {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public void add(int number) {
if(map.containsKey(number)) {
map.put(number, map.get(number) + 1);
} else {
map.put(number, 1);
}
}
public boolean find(int value) {
for(int key : map.keySet()) {
int another = value - key;
if(another == key && map.get(key) > 1) {
return true;
} else if(another != key && map.containsKey(another)) {
return true;
}
}
return false;
}
}

https://leetcode.com/discuss/19562/java-solution-o-n-add-o-1-find-and-o-n-space
O(n) add, O(1) find
public class TwoSum { Map<Integer, Integer> numToCountMap = new HashMap<>(); Set<Integer> sums = new HashSet<>(); public void add(int number) { for (Integer ele : numToCountMap.keySet()){ sums.add(number + ele); } Integer counts = numToCountMap.get(number); counts = (counts == null) ? 1 : counts+1; numToCountMap.put(number, counts); } public boolean find(int value) { return sums.contains(value); } }

Use 2 hashsets. - we don't care the count.
void add(int number) { for(const auto& num:numSet) sumSet.insert(num+number); numSet.insert(number); } bool find(int value) { return sumSet.find(value)!=sumSet.end(); } private: unordered_set<int> numSet, sumSet;
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=159612&pid=2122139&page=1&extra=page%3D5%26filter%3Dsortid%26sortid%3D311#pid2122139
--> list is not good - as the data may contain duplicates
-> we don't need the count in the map.
public class TwoSumTest2 implements TwoSum{
private HashMap<Integer, Integer> map;
private ArrayList<Integer> list;
int lastIndex;

public TwoSumTest2(){
      map = new HashMap<Integer, Integer>();
      list = new ArrayList<Integer>();
      lastIndex = 0;
}

public void store(int input){
      list.add(input);
      for(int i =1; i<= lastIndex;i++){
      map.put(list.get(i)+input,1);
      }
      lastIndex++;
}

public boolean test(int val){
      if (map.containsKey(val)){
      return true;
      }
      return false;
}
}

Not good, just different:

https://leetcode.com/discuss/76823/beats-100%25-java-code
I found that using a count map alone is twice as slow. Do you have any idea why?

This is very interesting, using approach utilizing Map.Entry is good, such as https://leetcode.com/discuss/19515/my-solutions-java-and-python-time-for-add-time-for-find-space. but still performed much worse than using a list like this one.

I think it is due to HashSet iterator traversing overhead, comparing to good-old positional traversing.

Actually HashMap<Integer, Boolean> would do the job, no need of HashMap<Integer, Integer>

Map<Integer, Boolean> num2dupMap = new HashMap<Integer, Boolean>(); // Add the number to an internal data structure. public void add(int number) { // add number to a map, if already exist, set it to true num2dupMap.put(number, num2dupMap.containsKey(number)); } // Find if there exists any pair of numbers which sum is equal to the value. public boolean find(int value) { // for each of the number in the map, get the (value - number) // try to find (value - number) in the map // if it exits in the map, for(Entry<Integer, Boolean> entry: num2dupMap.entrySet()){ int num1 = entry.getKey(); int num2 = value - num1; if (num1 == num2 && entry.getValue()){ // 1. could be number2 = (value - number1) hence to make sure it not only // just found the original number, but a 2nd number of the same value, // we need to && map.get(number2) == true // then return true return true; } else if (num1 != num2 && num2dupMap.containsKey(num2)){ // 2. could be number2 != (value - number1), and if we `enter code here`found it, we // found a winner return true; } } return false; }
https://leetcode.com/discuss/52158/java-ac-solution-with-avl-tree
https://leetcode.com/discuss/oj/two-sum-iii-data-structure-design
You can further reduce the space complexity by not using the List list and use the keyset of Map to iterate over the added integers.
public class TwoSum { List<Integer> list = new ArrayList<Integer>(); Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // Add the number to an internal data structure. public void add(int number) { list.add(number); if (map.containsKey(number)) map.put(number, map.get(number)+1); else map.put(number, 1); } // Find if there exists any pair of numbers which sum is equal to the value. public boolean find(int value) { for (int i = 0; i < list.size(); i++) { int num1 = list.get(i); int num2 = value - num1; if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) return true; } return false; }
https://leetcode.com/discuss/76146/trade-off-in-this-problem-should-be-considered
public class TwoSum { Set<Integer> sum; Set<Integer> num; TwoSum(){ sum = new HashSet<Integer>(); num = new HashSet<Integer>(); } // Add the number to an internal data structure. public void add(int number) { if(num.contains(number)){ sum.add(number * 2); }else{ Iterator<Integer> iter = num.iterator(); while(iter.hasNext()){ sum.add(iter.next() + number); } num.add(number); } } // Find if there exists any pair of numbers which sum is equal to the value. public boolean find(int value) { return sum.contains(value); } }

Extended: how about 3 sum or k sum.
-- use TreeMap<Integer, Integer> dict = new TreeMap<>(); ??

X. Binary Search Tree
https://www.bbsmax.com/A/1O5E9lAy57/

第一种，使用一个数组去存所有加入的元素，使用一个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咯。


    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;
        }
    }
}

注意到撸主注释的部分，有一个优化。就是在插入和搜索过程中，沿途找到的sum我们缓存起来，下次说不定可以用。Find的之前可以先在seenset里面看看。

Read full article from leetcode 170: Two Sum III - Data structure design - 西施豆腐渣 - 博客频道 - CSDN.NET

leetcode 170: Two Sum III - Data structure design

Labels

Popular Posts