Time limit for 3sums in java


  • 0
    S
    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
        	List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        	//Queue<Integer>  q = new LinkedList<Integer>();
        	if(nums.length<3){
        		return resultList;
        	}
        	//快排
    		this.quickSort(nums,0,nums.length-1);
    		//two sums
    		for(int i=0;i<nums.length-2;i++){
    			int start = i + 1,end = nums.length - 1;
    			while(start < end){
    				List<Integer> result = new ArrayList<Integer>();
    				if(nums[start]+nums[end]>nums[i]*(-1)){
    					end--;
    				}else if(nums[start]+nums[end]<nums[i]*(-1)){
    					start++;
    				}else{
    					result.add(nums[i]);
    					result.add(nums[start]);
    					result.add(nums[end]);
    					if(resultList.indexOf(result)==-1){
    						resultList.add(result);
    					}
    					start++;
    					end--;
    				}
    			}
    		}
    		return resultList;
        }
        /**
         * 快速排序
         * @param 待排序的数组
         * @param 开始位置
         * @param 结束位置
         */
        public void quickSort(int [] t,int start,int end){
         if(start < end){
    		int i = start,j = end;
    		int key = t[start];
    		while(i<j){
    			while(j>i&&t[j]>=key){
    				j--;
    			}
    			if(i<j){
    				t[i] = t[j];
    				i++;
    			}
    			while(i<j&&t[i]<=key){
    				i++;
    			}
    			if(i<j){
    				t[j]= t[i];
    				j--;
    			}
    		}
    		t[i] = key;
    		this.quickSort(t, start, i-1);
    		this.quickSort(t, j+1, end);
          }
        }
    }

  • 2
    R

    I was able to fix the TLE by adding line

    if (i>0 && nums[i]==nums[i-1]) continue;
    

    just after the line with the for loop:

    for(int i=0;i<nums.length-2;i++){
    

    The added line speeds up the algorithm by skipping duplicate searches that start with the same first number (nums[i]).


  • 0
    S

    It's a great idea! Thank you very much!


Log in to reply
 

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