# Untitled

unknown
plain_text
a month ago
1.7 kB
0
Indexable
Never
```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]);
valueToIndices.put(nums[i], existingIndices);
} else {
List<Integer> newList = new ArrayList<>();
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;

}
}```