O(n) time O(n) space solution in Java


  • 15
    Z

    Use a map to cahce each element seen so far. While scanning the array left to right , for each element nums[i] check if there is a number K in cache such that A[i] + k = target. That means we need to find in cache for k = target-A[i].

    public class Solution {
        public int[] twoSum(int[] nums, int target) {
            int[] res = new int[2];
            res[0] = -1;
            res[1] = -1;
    
            final HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
    
            for (int i = 0; i < nums.length; i++) {
                if (h.containsKey(target - nums[i])) {
                    int index = h.get(target-nums[i])+1;
                    res[0] = Math.min(i+1, index);
                    res[1] = Math.max(i+1, index);
                }
                h.put(nums[i], i);
            }
    
            return res;
        }
    }

  • 0
    S

    you are gooooooood!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


  • 0
    Y

    the containsKey is not O(1). So it's not O(n);


  • 0
    Z

    if there is no null key than contains key and get are same and so containsKey() is O(1) with consistent hashing. If you still are not satisfied then you can use get and check against null for key existence.


  • 0
    D

    NiuBi!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


  • 0
    N

    containsKey is O(1). This solution is good


  • 0
    A

    index is for sure the first one to be output, right? So there's no need to use the function Min() or Max()?


  • 0
    R

    Good idea,Buf if h.containsKey(target - nums[i]==true,maybe it's time to break out the loop and return!


  • 0
    A

    I don't understand if the complexity of this algorithm is O(n), why it's runtime cannot beat the O(nlogn) algorithm (posted at https://leetcode.com/discuss/7412/my-o-nlogn-and-o-n-time-complexity-solution-with-o-n-space)? I'm new coder. Would you please explain it? thanks a lot.


  • 0
    Z

    The other solution uses o(lgn) binary search to find the matching hence it is o(nlgn) . My solution used o(1) time hashmap to find the match. Hence it is io(n). However my solution uses o(n) memory and the other solution doesn't use any extra memory. So there is always a trade-off and I selected to go with extra memory as memory is cheap for the sake of runtime performance.


  • 0
    N

    it depends on the test case and the algorithms itself. And by the way, many many factor will affect the rt of the algorithm. Even the rt of two o(n) algorithm may vary greatly. For example, hashMap is o(1) for looking up a element by a key, but it's really slow. It's o(1) because the rt will not increase as much as the n increase . When the test case is small and you use the hash map, maybe your algorithm will be very slow.


  • 0
    Z

    This is a simple premitive key type hashmap so not much collision and resizing. You are not correct when saying that hashmap lookup is skower than binary search. It's not and we shouldn't argue online about it. If you want we can discuss offline zahidbuet106@gmail.com


  • 0
    N

    I don't want to discuss it. You have to know that I am not saying that hashmap is slower than binary search. I said it depend on the test case. And when the test case is small, the o(1) solution may be not beat the o(logn) solution because the coefficient is big(for hashtable is not small, especially when you have to do the boxing and the unbonxing and create the hashtable object). If you do not agree with me, it's totally ok.


  • 0
    N

    And I have to say that your solution is excellent.


Log in to reply
 

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