LeetCode: 1.Two Sum

Posted on Edited on In

Problem Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Wrong Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int[] res = new int[2];
        for (int i =0; i <nums.length; i++){
            hashMap.put(nums[i], i);
            if(hashMap.containsKey(target-nums[i])){
                res[0] = i;
                res[1] = hashMap.get(target-nums[i]);
            }
        }
        return res;
    }
}

Error Information

When nums= [3, 3], target = 6，expected outcome is[0, 1]，but [1, 1].

Wrong Thinking

I was trying to store the array into a hashmap. Considering that hashmap can only get value from key, so I put the value of array at the place of K while incremental i is V.
Then reason why I was wrong was not considering the situation of repeated numbers. During the debugging I found that the size of hashMap is 1 when the nums=[3,3] which means key is unique in hashMap.

How Did I Correct the Code

Review

The key of making mistake is ignoring the situation of repeated numbers in array, so directely transform array into hashmap by reversing the index to value is not feasible since the repeated numbers won’t be stored twice in hashmap as a key.

Analysis

Given that the input would have exactly one solution, and the same element won’t be used twice, situation like multi-resolution and non-resolution will not be considered.
Because hashMap can get value by key, we still need hashmap to do this but in another way.
Instead of transforming the array into hashmap one time, I decide to use hashMap.containskey(target-nums[i]) to search the hashmap, if returns false, then I put this number into the hashmap instead, otherwise we can get the right answer.
If the number is repeated but still cannot find the answer, then it means the resolution is not unique which doesn’t obey the rule of question. For example: nums = [3, 3, 6], target = 9. Obviously, the solution is not unique.

Right Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++){
            if (hashMap.containsKey(target-nums[i])){
                res[0] = hashMap.get(target - nums[i]);
                res[1] = i;
            }else {
                hashMap.put(nums[i], i);
            }
        }
        return res;
    }