Why is this a TLE


  • 0
    H

    It runs quite fast with the TLE case in my mac, I cannot find the time consuming bug. Help.

    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for(int i = 0; i < nums.length-2; i++){
                if(i > 0 && nums[i] == nums[i-1]) continue;
                int target = - nums[i];
                if(target<0) break;
                Map<Integer, Integer> m = new HashMap<>();
                for(int ii = i+1; ii < nums.length; ii++){
                    
                    if(m.get(nums[ii]) != null){
                        res.add(Arrays.asList(nums[i], nums[m.get(nums[ii])], nums[ii]));
                    } else{
                        m.put(target - nums[ii], ii);
                        while(ii+1 < nums.length && nums[ii+1] == nums[ii]) ii++;
                    }
                }
            }
            return res;
        }
    }

  • 0
    C

    Did read the code carefully. But... from your description (runs correctly on mac but TLE on OJ), I guess the creation of hashmap is the root cause.


  • 0
    H

    python would pass
    similar problem with java versus python: https://leetcode.com/discuss/50701/python-ac-but-java-mle. I don't know java fails so often


  • 0
    H

    change to linked list got ac


Log in to reply
 

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