simple solution with O(n^2) Algorithm complexity


  • 2
    B

    First, sort the nums by Arrays.sort(); Algorithm complexity is O(n log n);
    then, use i point to the start position, j point the next of i, k point to the tail;
    Three condition: the sum of these three num higher, lower, or equal to zero;
    Three solution:
    higher: we need the highest num become lower, so k--;
    lower: the opposite of higher condition, j++;
    equal: add to the ArrayList<Integer> and save into the HashSet<List<Integer>>. Except this condition, we ignore the other nums between j and k, so j++, k--;
    '''
    public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);

    	Set<List<Integer>> set = new HashSet<List<Integer>>();
    	int len = nums.length;
    	int i = 0;
    	int j = 0;
    	int k = 0;
    	while(i < len) {
    		j = i + 1;
    		k = len - 1;
    		while( j < k ) {
    			if((nums[i] + nums[j] + nums[k]) < 0) {
    				j++;
    			}else if((nums[i] + nums[j] + nums[k]) > 0){
    				k--;
    			}else {
    				List<Integer> subList = new ArrayList<Integer>();
    				subList.add(nums[i]);
    				subList.add(nums[j]);
    				subList.add(nums[k]);
    				set.add(subList);
    				j++;
    				k--;
    			}
    		}
    		i++;
    	}
    	return new ArrayList<>(set);
    }
    

    '''


  • 1
    P

    You can save 5 lines in the else { by never naming subList:

    set.add(Arrays.asList(nums[i], nums[j], nums[k]));

    And 2 more by making the outer while loop a for loop:

    int len...
    for(int i = 0; i < len; i++) {
        int j = i + 1;
        int k = len - 1;
        while ( j < k ) {
            ...
        }
    }
    return...
    

    Also, since the input array was sorted, you can avoid any Set<List> and form the returned List<List> directly by continuing to increment j until nums[j] is a different number (or j >= k) whenever j is incremented, and vice versa for k (whenever k is decremented, continue decrementing k until nums[k] has a different value, or k <= j) to avoid duplicate triplets. That results in more lines and doesn't help overall time complexity, but it does avoid use of Set.


  • 0
    This post is deleted!

Log in to reply
 

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