Does any one tell me why it sometimes got TLE and sometimes AC?


  • 0
    M
    public List<List<Integer>> threeSum(int[] nums) {
         if(nums.length < 3) return new ArrayList();
    	        List<List<Integer>> res = new LinkedList();
    	        HashMap<List, Boolean> hm = new HashMap();
    	        Arrays.sort(nums);
    	        for(int i = 0; i < nums.length - 2; i++){
    	        	int start = i + 1, end = nums.length - 1;
    	        	while(start < end){
    	        		while(start < end && nums[i] + nums[start] + nums[end] < 0)
    	        			start++;
    	        		while(start < end && nums[i] + nums[start] + nums[end] > 0)
    	        			end --;
    	        		if(start < end && nums[i] + nums[start] + nums[end] == 0){
    	        			List<Integer> arr = new ArrayList(Arrays.asList(nums[i], nums[start], nums[end]));
    	        			if(!hm.containsKey(arr)){
    	        				res.add(arr);
    	        				hm.put(arr, true);
    	        			}
    	        				
    	        			start ++;
    	        			end --;
    	        		}		        	
    	        	}
    	        }
    	        return res;

  • 0

    I just submitted this five times and got TLE every time. With ArrayList I got TLE in the first attempt and then AC in the second attempt. Also you don't have any inserts, only appends.


  • 0
    M

    Oh, yeah, I resubmit this code and got TLE, too. I don’t quite get what’s wrong with it...


  • 0
    D

    3 situations to consider:
    1)nums[end],num[end-1],nums[end-2] ... nums[end-n]. If all equals to same value, then you have to skip all them and go nums[end-n-1] directly.
    2)Same thing to nums[start]
    3)if nums[start]>0, or nums[end]<0, then no need to run on.
    Wasted me a long time on this. I think leetcode is just going into a wrong direction on this TLE thing.


Log in to reply
 

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