[LeetCode III – data structure design of the sum of two Numbers] | punch brush

Has been the habit of brush, recently saw the nuggets held a brush activities, especially to participate in! This topic is question 5.

This article is participating in the nuggets team online activity, clickCheck spring recruitment positions in big factories

I. Title Description:

Sum of two numbers III- Data structure design

describe

Design B and implement a TwoSum class. He needs to support the operations add and find. Add – Adds this number to the internal data structure. Find – Whether there is any pair of numbers whose sum equals this value

The sample

Sample 1:

add(1); add(3); add(5); Find (4)// returns true find(7)// returns falseCopy the code

Ii. Analysis of Ideas:

methods	describe	Time complexity	Spatial complexity
Double pointer	The following code implementation	Add and find are both $O(N)$	$O(N)$
Hash method	The following code implementation	The add is $O(1)$The find is $$O (N)	$(N)$

Iii. AC Code:

Hash method

? Advantage: add is fast O(1), no need to sort like a double pointer

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    private Map<Integer, Integer> counter;

    public TwoSum(a) {
        counter = new HashMap<>();
    }

    / * * *@param number: An integer
     * @return: nothing
     */
    public void add(int number) {
        // write your code here
        // key is value,value is [origin value + 1,0 + 1]
        counter.put(number, counter.getOrDefault(number, 0) + 1);
    }

    / * * *@param value: An integer
     * @return: Find if there exists any pair of numbers which sum is equal to the
     *          value.
     */
    public boolean find(int value) {
        // write your code here
        for (Integer key : counter.keySet()) {
            // searchKey + key == value
            int searchKey = value - key;
            int reulstCount = key == searchKey ? 2 : 1;
            if (counter.getOrDefault(searchKey, 0) >= reulstCount) {
                return true; }}return false; }}Copy the code

Double pointer

! Disadvantages: Timeout occurs when the amount of data is large

Code implementation

public class TwoSum {
    List<Integer> mSums ;
    public TwoSum(a){
        mSums = new ArrayList<>();
    }
    / * * *@param number: An integer
     * @return: nothing
     */
    public void add(int number) {
        // write your code here
        mSums.add(number);
        // sort array
        int index = mSums.size() -1;
        // keep ascending order
        while(index > 0 && mSums.get(index-1) > mSums.get(index) ){
            // left value > right value
            // swap
            int temp = mSums.get(index);
            mSums.set(index,mSums.get(index-1));
            mSums.set(index-1,temp); index --; }}/ * * *@param value: An integer
     * @return: Find if there exists any pair of numbers which sum is equal to the value.
     */
    public boolean find(int value) {
        // write your code here
        int left = 0 ;
        int right = mSums.size()-1;
        while(left<right){
            int currentSum = mSums.get(left)+mSums.get(right);
            if(currentSum < value){
                left++;
            }else if(currentSum >value){
                right--;
            } else{
                return true; }}return false; }}Copy the code

Iv. Summary:

Data structure design is the ability to use data structures.

• Even though we can solve this problem with double Pointers, we’re usingListStructure, the disadvantage is the large amount of data timeout, does not conform to the meaning of the question.
• A good practice is to use hash tables, which have the advantage of dynamic inserts and deletions, no sorting, and no timeouts for large data volumes.
• After finishing the questions, you can answer themListwithMapThe difference is better, the general answer idea is:
  1. This paper introduces the ADT abstract interface, that is, the exposed interface
  2. How do you implement the underlying interface, and if so, how do you implement it
  3. The difference between access, who accesses dynamically and who accesses statically
  4. The difference between operations, who operates dynamically and who operates statically