Java - Leetcode Two Sum Hashmap Solution

I'm new to Java and I just started to do Leetcode - Two Sum. I found that except brute force solution, the common solution is using Hashmap. But I still cannot get it. For example, this works in my logic:

public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); int[] res = new int[2]; for (int i = 0; i < nums.length; ++i) { m.put(nums[i], i); } for (int i = 0; i < nums.length; ++i) { int t = target - nums[i]; if (m.containsKey(t) && m.get(t) != i) { res[0] = i; res[1] = m.get(t); break; } } return res; } 

The first for loop put numbers to Hashmap, and use the second for loop to check if we can find the number that equals to target number - nums[i]. However, I saw a lot of accepted solutions combined the two for loops, such as this example:

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

In my logic, the second solution run the for loop like this:

//[2,7,11,15] when i=0, m.put(nums[0],2) when i=1, m.put(nums[1],7) when i=2, m.put(nums[2],11) when i=3, m.put(nums[3],15) 

And because i < nums.length so when i=4, the code will jump to return res. It won't run the for loop again. But as far as I know, I saw people say that the second solution will iterate through the array, and store the index and value to Hashmap and then iterate again. In my imagination there's only one for loop, how can they use the only one for loop to iterate again?

2 Answers

there wont be any 2nd iteration. In one iteration itself the loop would break if a pair is found.

consider this:

//[2,7,11,15] and target = 13 when i=0, m.put(mums[0],2) when i=1, m.put(mums[1],7) when i=2, m.contains(13 - mums[2]) == true // since 13 - 11 = 2 is present at index 0 res[0] = 2 res[1] = 0 break; 

and Hence, ..... you are right. there is only one iteration.

There is no need for two for loops and this can be done in the single for loop as posted by you.From a perfomance point of view its better to iterate only once in the for loop and break from the loop when the first matching pair is found. This is O(n) in the worst case.

 public static int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { int rem = target - num; if (map.containsKey(rem)) { return new int[] { num, rem }; } map.put(num, num); } // for return null; } 

ncG1vNJzZmirpJawrLvVnqmfpJ%2Bse6S7zGiorp2jqbawutJobGxrZWiAeYSOo5ivmV2hsqbAwqibnmWkrLxuv9SmZKGZo526oryMrKalraSevK8%3D