Java HashSet Time Limit Exceed and Solve it.


  • 0
    L

    I have faced TLE problem with a solution using HashSet. This should be a O(n) solution and fast enough, but to finally I use a O(nlogn) algorithm by first sort the array and then check if there exist same value and get passed.

    This must be something wrong with test case and don't get stuck in this simple problem.


  • 0
    D

    AC solution, the should be some problem in your code, show it if needed.

            if(nums == null) return false;
            HashSet<Integer> set = new HashSet<Integer>();
            for(int num: nums){
                if(set.contains(num)) return true;
                set.add(num);
            }
            return false;
        
    

  • 0
    L

    @D.Q.Zhang Here is the code.

    public class Solution {
        public boolean containsDuplicate(int[] nums) {
            Set<Integer> set = new HashSet<Integer>();
    		for(int i : nums)
    			if(!set.add(i))
    				return true; 
    		return false;
        }
    }
    

    I try it again after seeing your post and it get passed. I really don't know why.


  • 0

    @D.Q.Zhang My code is exactly the same as yours, but I got TLE

    public boolean containsDuplicateV1(int[] nums) {
    	Set<Integer> set = new HashSet<Integer>();
    	for (int num : nums)
    		if (set.contains(num))
    			return true;
    		else
    			set.add(num);
    	return false;
    }
    

  • 1
    Y

    @keZhenxu You should not use contains function here.If you use contains here,it will cost extra time to find if the element exist or not.Actually,the add function will return true if the element isn't in the set,vise versa.So,you can simplify your code into:
    for(int i : nums)
    if(!set.add(i))
    return true;


  • 0

    @yliu224 Indeed, Thankds!


  • 0

    @yliu224 Thank you !! You really helped me out


Log in to reply
 

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