What do you mean "use hash"? can you add code?


  • 0
    S

    Can you add the code for hash sort?

    Thanks!!!


  • 1
    M

    It doesn't mean adding a hash sort, just storing the values you've already obtained in a dictionary or other hashing storage object. Your original solution assumes that each index in turn is the first value, and checks all following values to see if it is true. By using a hash, you can store the numbers you've seen, and then just look for the second one.

    A hash has O(1) lookup, so for each element, you can check "have I already seen an element that matches my current element?" in O(1) time instead of checking each of them in turn. This drops your solution from O(n^2) to O(n).

    As pseudocode:

    Find the pair of elements where they sum to n.

    for each element a in the array {
        is n-a stored in the dictionary?
        if yes, return [dictionary[n-a], index of a]
        if no, store dictionary[a] = index of a
    }
    return [0,0] //to stop complaints, will never run
    

    PS As a warning: For the outputs, the indexes need to be 1-based, not 0-based.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.