Accepted Java O(n) Solution


  • 312
    J

    Hi, this is my accepted JAVA solution. It only go through the list once. It's shorter and easier to understand. Hope this can help someone. Please tell me if you know how to make this better :)

    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                result[1] = i + 1;
                result[0] = map.get(target - numbers[i]);
                return result;
            }
            map.put(numbers[i], i + 1);
        }
        return result;
    }

  • 3
    S

    what a neat solution


  • 4
    D

    Nice solution!


  • 14
    B

    Great minds think alike. :-)

    public class Solution {
    	public int[] twoSum(int[] numbers, int target) {
    	    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for (int i = 0; i < numbers.length; i++) {
    		    if (map.containsKey(numbers[i])) {
    		        return new int[]{map.get(numbers[i]) + 1, i + 1};
    		    } else {
    		        map.put(target - numbers[i], i);
    		    }
    		}
    		return new int[]{0, 0};
    	}
    }
    

  • 44
    T

    it actually o(nlogn), logn is time find the element or insert the element to the map


  • 7
    D

    I think you are drunk @thuang...How could it be logN


  • 3
    F

    if u used a map, then the time to insert or find an element is about logN. isn't is right?


  • 0
    X

    Elegant code!


  • 2
    H

    Keep in mind, It's HashMap not TreeMap.


  • -3
    H
    This post is deleted!

  • 4
    L

    Wow! This is brilliant! I was thinking to sort first then use two pointers.


  • 0
    C

    very easy to understand!


  • 0
    H

    Then you should use abacus, not a computer


  • 30
    H

    Shortened your code as

    public int[] twoSum(int[] numbers, int target) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int i = 0; i < numbers.length; map.put(numbers[i], ++i)) 
                if (map.containsKey(target - numbers[i])) 
                    return new int[]{map.get(target - numbers[i]),i+1};
            return new int[]{0,0};
        }

  • 1
    S

    I'm sure it's not an O(n) solution.
    Using c++.
    I sorted it first then search for answer cost 60ms.
    Also in c++, your algorithm cost 68ms.


  • 7
    D

    In C++, the running time of map's get is O(logn), not O(1). In Java, we have O(1) get, so it's O(n).


  • 0
    Z

    I think the time is not O(n).You not count the time of Operation in map.Please forgive me for my Chinglish.


  • 0
    J

    it's a good idea to start i from 1, and at the same time make j<i in the inner loop. This really reduces the time of loops. But i don't think "if(j<i)break;" makes any sense. It makes no difference if we don't have this line of code.


  • 1
    J

    I am sure that in Java it's O(n), I guess in C++ it's not. Thanks for pointing out :)


  • 0
    H

    Just because I only have a text editor when writing this piece.And I'm not sure how map saves time.


Log in to reply
 

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