Do not worry about duplicate numbers in the array

  • 0

    We can see a lot of HashMap solutions using a HashMap to store the number as the key and the index as the value.

    Many people will come up the same questions that what if there have duplicate numbers in the array?

    Well, it's not a problem at all. Because in the description, it says there is exactly one solution. I will prove it here:

    1. Say we have three N1 in the array like this [N1, N2, N1, N3, N1], then N1 will not be part of the result with N2 or N3, since if N1 is part of the result, then we have three solutions which go against the description. N1 cannot be part of result with itself neither since then we have three solutions again. So in this case, we do not care duplicates at all.

    2. So the only possible situation that the N1 can be the result is: N1 MUST only have two of them, and the target MUST be 2 * N1, then we have an array like this: [N1, N2, N1], and a target like this 2 * N1. In this case, after building up the map, N1's index will be the right most one which is 2. Then when we start from the first N1 at index 0, we do (target - N1) and get N1, and then query the N1's index in the array, which is 2, and then we can get the result which is [0, 2] with no problem.

Log in to reply

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