LeetCode - Two Sum

Problem description

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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Analysis

the first thought is to use HashMap in Java to store the value of integer as key and index as the value of HashMap, so that we can find corresponding index quickly.

Here’s the code:

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> vals = new HashMap<>();
    int index = 0;
    for(int i:nums){
      vals.put(i, index++);
    }

    index =0;
    for(int i:nums){
      if (vals.containsKey(target - i)){
        int[] res =new int[2];
        res[0] = index;
        res[1] = vals.get(target - i);

        // miss this part, need to remember
        if (res[0] == res[1]){
          index++;
          continue;
        }
        return res;
      }
      index++;
    }

    return new int[]{};
  }

I missed the using same value only once part, so get a WA in the first time submission.

The time complexity is O(n), but read the array twice.

A better solution is to read it once.

Here’s the code:

public int[] twoSum(int[] nums, int target) {
    if (nums == null) {
        return null;
    }
    int index = 0;
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums) {
        if (map.containsKey(target - num)) {
            return new int[] {map.get(target - num), index};
        }
        map.put(num, index++);
    }
    return null;
}

What to improve

• read the description carefully

• missing null checking

if (nums == null) {
    return null;
}

• short code for return an array

return new int[] {map.get(target - num), index};

• error state return(need to be clarified)

return null;