Java solution with O(n^2) complexity (8ms)


  • 0
    V
    public List<List<Integer>> threeSum(int[] nums) {
    	List<List<Integer>> theTripletsColl = new ArrayList<>();
    	Arrays.sort(nums);
    	for (int i = 0; i < nums.length-2; i++) {
    		int thePivot = -nums[i];
    		int pre = i+1, end = nums.length-1;
    		while(pre < end) {
    			if(nums[pre] + nums[end] == thePivot) {
    				theTripletsColl.add(Arrays.asList(nums[i], nums[pre] , nums[end]));
    				do{pre++;}while(pre < end && nums[pre-1] == nums[pre]);
    				do{end--;}while(pre < end && nums[end+1] == nums[end]);
    			} else if (nums[pre] + nums[end] < thePivot) {
    				pre++;
    			} else {
    				end--;
    			}
    		}
    		//skip the same result
    		while(i < nums.length-2 && nums[i+1] == nums[i]) i++;
    	}
    	return theTripletsColl;
    }

  • 0
    N

    your solution gets a TLE with the following test set:
    [7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6]


  • 0
    V

    well, are you sure? cause i run it again and it turns out to be fine...


Log in to reply
 

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