Simple one pass Java solution beats 80%


  • 0
    L

    A typical solution would be an n^2. However, the trick is to use an auxiliary data structure to gain efficiency at the cost of additional space. Since duplicates are possible, it is best to use the map as we go rather than saving everything in one pass. This is demonstrated below:

    public int[] twoSum(int[] nums, int target) {
           int[] ret = new int[] {};
           if(nums.length==0) {
               return ret;
           }
           Map<Integer,Integer> map = new HashMap<>();
           for(int i=0;i<nums.length;i++) {
               Integer idx = map.get(target-nums[i]);
               if(idx!=null) {
                   return new int[] {idx,i};
               }
               map.put(nums[i],i);
           }
           return ret;
        }
    

Log in to reply
 

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