Is this question cannot use hash table as the solution?


  • -1
    L

    I think building a hash table is a direct method for solving this problem which use the value as the key and the index as the value. However some test cases may have duplication in the array, for example the [0,4,3,0]. So does that mean this problem cannot be solved using hash table?

    Thanks


  • 0
    L

    it is wrong for duplicate element if using hash or dictionary


  • 0
    Z

    //if have duplicates, the indices must be the first dup and the last one. E.g, [0,0,0], 0 should return [1,3] not [1,2]. Seems so.
    public class Solution {
    public int[] twoSum(int[] nums, int target) {
    int [] ret=new int[2];
    Map<Integer, Integer> hm=new HashMap<Integer,Integer>();
    int n=nums.length;
    for(int i=0;i<n;i++){
    int diff=target-nums[i];
    if(hm.containsKey(diff)){
    ret[0]=hm.get(diff)+1;
    ret[1]=i+1;
    }else{
    hm.put(nums[i],i);
    }
    }
    return ret;
    }

    }


  • 0
    J

    "You may assume that each input would have exactly one solution.", so [0,0,0], 0 is not a valid test case, only [0,0,1], 0 is allowed.


  • 2
    J

    We can use hash map to solve the problem:

    1. Traverse the array by index one by one
    2. if target - num[i]` is in the map, then we found answer # NOTICE: we find answer but we don't insert the second answer into the map, so the duplicate number is not a problem.
      else insert <num[i], i> into the map.

Log in to reply
 

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