Java using HashMap, O(n) sol.


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

  • -2
    Y

    Firstly, it's not O(n), but O(n^2), just more fast than bubble sort, which is because of hash index.
    you can use quick sort to achieve O(nlogn) which can beats 90% solutions.


  • 0
    O

    Could you explain where did you see O(n^2) time complexity? How did you count complexity here? I also see only O(n) time and space complexity as HashMap get value in O(1) space complexity.


  • 0
    T

    Do you know why it's so slow? I use the same method ,but it is slower than quick sort..


Log in to reply
 

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