One of the interesting problem to solve is Two Sum

**First Solution**

My first assumption from the problem was that input will be always sorted, and obviously leetcode bot rejected the solution.

public class Solution { public int[] twoSum(int[] numbers, int target) { int[] result = new int[2]; int l = 0; int r = numbers.length - 1 ; while (l < r) { if (numbers[l] + numbers[r] == target) { result[0] = l + 1; result[1] = r + 1; break; } else if (numbers[l] + numbers[r] < target) { l++; } else { r--; } } return result; } }

After fixing that issue, I forget about duplicate entries

public class Solution { public int[] twoSum(int[] numbers, int target) { java.util.Map<Integer, Integer> numMap = new java.util.HashMap<Integer,Integer>(); for ( int i = 0; i < numbers.length; i++) { numMap.put(numbers[i], i + 1); } Arrays.sort(numbers); int[] result = new int[2]; int l = 0; int r = numbers.length - 1 ; while (l < r) { if (numbers[l] + numbers[r] == target) { result[0] = numMap.get(numbers[l]); result[1] = numMap.get(numbers[r]); break; } else if (numbers[l] + numbers[r] < target) { l++; } else { r--; } } return result; } }

Here is the accepted Solution

public class Solution { public int[] twoSum(int[] numbers, int target) { java.util.Map<Integer, java.util.List<Integer>> numLocationMap = new java.util.HashMap<Integer, java.util.List<Integer>>(); for (int i = 0; i < numbers.length; i++) { java.util.List<Integer> indexList = numLocationMap .get(numbers[i]); if (indexList == null) { indexList = new java.util.ArrayList<Integer>(); numLocationMap.put(numbers[i], indexList); } indexList.add(i + 1); } Arrays.sort(numbers); int[] result = new int[2]; int l = 0; int r = numbers.length - 1; while (l < r) { if (numbers[l] + numbers[r] == target) { if (numLocationMap.get(numbers[l]).size() == 1) { result[0] = numLocationMap.get(numbers[l]).get(0); result[1] = numLocationMap.get(numbers[r]).get(0); } else { result[0] = numLocationMap.get(numbers[l]).get(0); result[1] = numLocationMap.get(numbers[r]).get(1); } break; } else if (numbers[l] + numbers[r] < target) { l++; } else { r--; } } Arrays.sort(result); return result; } }

Advertisements