HashMap O(N^2 ) solution, but time out, why ?


  • 0
    G

    I use hashmap to solve this problem. Basic idea is to use a hashMap to store the integer as key and its last index as value. Then iterator through the list to find three elements that sum up to zero. Hash these three values into an integer and store in a hashset so that make sure no duplicate would be added to the result list. I think the algorithm is still O(N ^ 2) but why will it time out? Did I implement anything wrong?

    public List<List<Integer>> threeSum(int[] nums) {
            HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();//key is number, value is index
            for(int i =0; i < nums.length; i++){
                map.put(nums[i], i);
            }
            List<List<Integer>> result = new LinkedList();
            HashSet<Integer> duplicate = new HashSet<Integer>();
            for(int i =0; i < nums.length-2; i++){
                for(int j = i+1; j < nums.length-1; j++){
                    int sum = nums[i]+nums[j];
                    int rest = 0-sum;
                    if(map.containsKey(rest) && map.get(rest)> j){
                        int [] sort = new int[3];
                        sort[0]=nums[i];
                        sort[1]=nums[j];
                        sort[2]=rest;
                        Arrays.sort(sort);
                        int key = Arrays.hashCode(sort);// hash based on the content of array
                        if(!duplicate.contains(key)){
                            List<Integer> list = new LinkedList();
                            list.add(nums[i]);
                            list.add(nums[j]);
                            result.add(list);
                            duplicate.add(key);
                            list.add(rest);
                        }
                    }
                }
            }
            return result;
        }
    

Log in to reply
 

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