Why my java solution TLE?


  • 0
    J

    public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> lists = new LinkedList<List<Integer>>();
    Arrays.sort(nums);

    	int i, start, end, sum;
    	
    	for(i = 0; i < nums.length - 2 && nums[i] < 0; i++) {
    		if(i > 0 && nums[i - 1] == nums[i])
    			continue;
    		start = i + 1;
    		end = nums.length - 1;
    		while(start < end) {
    			sum = nums[i] + nums[start] + nums[end];
    			if(sum == 0) {
    				lists.add(Arrays.asList(nums[i], nums[start], nums[end]));
    				start++;
    				end--;
    				while((start < end) && nums[start] == nums[start - 1]) start++;
    				while((start < end) && nums[end] == nums[end + 1]) end--;
    			} else {
    				if(sum < 0) {
    					start++;
    					while((start < end) && nums[start] == nums[start - 1]) start++;
    				} else {
    					end--;
    					while((start < end) && nums[end] == nums[end + 1]) end--;
    				}
    			}
    			
    		}
    	}
    	
    	return lists;
    }
    

    }


  • 2
    R

    I can't reproduce it.

    What I see is that your solution throws compile error when the judge tries to verify it. The compile error is caused by the incorrect return type:
    List<List> instead of List<List<Integer>>.

    Another problem in your algorithm is that there is a too strict check in the for loop: && nums[i] < 0. This check doesn't work when the input is [0,0,0].

    The code was accepted for me after fixing these two problems:

    public List<List<Integer>> threeSum(int[] nums) { 
        List<List<Integer>> lists = new LinkedList<>(); 
        
        Arrays.sort(nums);
    
        int i, start, end, sum;
    
        for(i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
            if(i > 0 && nums[i - 1] == nums[i])
                continue;
            start = i + 1;
            end = nums.length - 1;
            while(start < end) {
                sum = nums[i] + nums[start] + nums[end];
                if(sum == 0) {
                    lists.add(Arrays.asList(nums[i], nums[start], nums[end]));
                    start++;
                    end--;
                    while((start < end) && nums[start] == nums[start - 1]) start++;
                    while((start < end) && nums[end] == nums[end + 1]) end--;
                } else {
                    if(sum < 0) {
                        start++;
                        while((start < end) && nums[start] == nums[start - 1]) start++;
                    } else {
                        end--;
                        while((start < end) && nums[end] == nums[end + 1]) end--;
                    }
                }
    
            }
        }
    
        return lists;
    
    }
    

  • 0
    J

    Thanks, I know what is wrong in my code.


Log in to reply
 

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