Untitled
unknown
plain_text
a year ago
1.7 kB
3
Indexable
class Solution { /** [2, 7, 11, 5] -> 9 9 - 2 Example: 2 -> look for 9 - 2 = 7 in the list Brute force, do this for each element-- bleh -> O(n^2) Optimize -> iterate once put the numbers in a hash map against indices containing that number iterate again, find the remaining value in the set */ public int[] twoSum(int[] nums, int target) { final Map<Integer, List<Integer>> valueToIndices = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (valueToIndices.containsKey(nums[i])) { final List<Integer> existingIndices = valueToIndices.get(nums[i]); existingIndices.add(i); valueToIndices.put(nums[i], existingIndices); } else { List<Integer> newList = new ArrayList<>(); newList.add(i); valueToIndices.put(nums[i], newList); } } int result[] = new int[2]; for (int i = 0; i < nums.length; i++) { int value = nums[i]; if (valueToIndices.containsKey(target - value)) { final List<Integer> indicesWithThisValue = valueToIndices.get(target - value); for (Integer otherIndex: indicesWithThisValue) { if (!otherIndex.equals(i)) { result[0] = i; result[1] = otherIndex; return result; } } } } return result; } }
Editor is loading...
Leave a Comment