Can anyone give a non-TLE solution?


  • 0
    S

    I find it seems that the classical O(n^2) solution can't pass because of TLE.

    Is there any pruning method or less than O(n^2) method?

    The classical solution means that first sort the array and then search the array with three index.


  • 0
    T

    I think the classical solution can solve the problem.
    How about this one?

    vector<vector<int> > threeSum(vector<int> &num) {
        
    if (num.size()<3) return vector< vector<int> > ();
    sort(num.begin(), num.end());
    vector< vector<int> > set;
    for(int id=0; id<num.size()-2; id++) {
        int ids = id+1, ide = int(num.size())-1;
        while(ids<ide && ids<num.size() && ide>=0) {
            if (num.at(ids) + num.at(ide) + num.at(id) == 0) {
                vector<int> ans(3, 0);
                ans.at(0) = num.at(id); ans.at(1) = num.at(ids);
                ans.at(2) = num.at(ide); 
                set.push_back(ans); 
                ids++; ide--;
                while(ids<num.size() && (num.at(ids-1) == num.at(ids)))
                    ids++;
                while(ide>id && (num.at(ide+1) == num.at(ide)))
                    ide--;
            }
            else if (num.at(ids) + num.at(ide) + num.at(id) > 0) 
                ide--;
            else ids++;
        }
        while((id+1)<int(num.size()) && (num.at(id+1) == num.at(id)))
            id++;
    }
    return set;
        
    }

  • 0
    S

    The simple O(n^2) solution will TLE. We need to do some prune for duplicated numbers. For the middle number of triplet, if it is the same to the previous two, then it can be skipped (the previous one is equivalent to it). Similar to the first and third element, we can also skip some elements, to reduce the time we need to judge duplicate of result.

    vector<vector<int> > threeSum(vector<int> &num) {
    	vector<vector<int> > result;
    	int n = (int)num.size();
    	if (n > 2) {
    		sort(num.begin(), num.end());
    		
    		for (int i = 1; i < n - 1; ++i) {
    			if (i > 2 && num[i] == num[i - 2]) continue;
    			int l = 0, r = n - 1;
    			while (l < i && r > i) {
    				if (l > 1 && num[l] == num[l - 1]) {
    					++l; continue;
    				}
    				if (r < n - 1 && num[r] == num[r + 1]) {
    					--r; continue;
    				}
    				int sum = num[l] + num[i] + num[r];
    				if (sum == 0) {
    					vector<int> item { num[l], num[i], num[r] };
    					bool flag = false;
    					for (int j = 0; j < result.size(); ++j) {
    						if (result[j][0] == num[l] && result[j][1] == num[i]) {
    							flag = true; break;
    						}
    					}
    					if (!flag) result.push_back(item);
    					++l; --r;
    				} else if (sum < 0) ++l; else --r;
    			}
    		}
    	}
    	return result;
    }

  • 0
    R

    Of course the O(N^2) should pass the TLE. The only thing you need to do is to remove the duplication during your O(N^2) process to save more time

    public List<List<Integer>> threeSum(int[] num) {
             // two pointer runner solution O(N^2 + NlogN)
            if (num.length < 3) return new ArrayList<List<Integer>>();
            Arrays.sort(num);
            List<List<Integer>> triplets = new ArrayList<>();
            for (int i = 0; i < num.length - 1; ) {
                int j = i + 1;
                int k = num.length - 1;
                while (j < k) {
                    int sum = num[i] + num[j] + num[k];
                    // remove duplication when you move i,j or k
                    if (sum > 0) while (num[k] == num[--k] && num[j] <= num[k] && j < k);
                    else if (sum < 0) while (num[j] == num[++j] && num[j] <= num[k] && j < k);
                    else {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(num[i]);
                        list.add(num[j]);
                        list.add(num[k]);
                        triplets.add(list);
                        while (num[k] == num[--k] && num[j] <= num[k] && j < k);
                        while (num[j] == num[++j] && num[j] <= num[k] && j < k);                          
                    }
                }
                while (num[i] == num[++i] && i < num.length - 2);
            }
            return triplets;  
        }

  • 0
    L

    Hi renli3000, since the array is already sorted, j < k guarantees num[j] <= num[k], right?


  • 1
    A

    Here's a solution in java using hashmap. surprising simple... the key is sorting help skipping all duplicates , that help in two ways. 1) reduciung further the processing time 2) skip duplicated output. the hashmap only keeps the largest index with same value, so the size will be small too.

    HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    	
    public LinkedList<LinkedList<Integer>> threeSum(int[] num) {
    	Arrays.sort(num);
    	LinkedList<LinkedList<Integer>> llll = new LinkedList<LinkedList<Integer>>(); 
    	for (int i = 0; i< num.length; i++) hm.put(num[i], i);
    	for (int i = 0; i<num.length; i++){
    		if (i > 0 && num[i] == num[i-1]) continue;
    		for (int j = i+1; j<num.length; j++){
    			if (j > i+1 && num[j] == num[j-1]) continue;
    			if (hm.containsKey(0-num[i] - num[j])){
    				if (hm.get(0-num[i]-num[j]) > j){
    					// we found a match
    					LinkedList<Integer> ll = new LinkedList<Integer>();
    					ll.add(num[i]);
    					ll.add(num[j]);
    					ll.add(0-num[i] - num[j]);
    					llll.add(ll);
    				}
    					
    			}
    		}
    	}
    	return llll;
        
    }

  • 4
    R

    I guess my code is somewhat easier to understand.

    public class Solution {
    	public List<List<Integer>> threeSum(int[] num) {
    		List<List<Integer>> results = new LinkedList<List<Integer>>();
    		if (num==null||num.length<3) return results;
    		
    		Arrays.sort(num);
    		for (int i = 0; i < num.length-2; i++) {
    			if (i>0&&num[i]==num[i-1]) continue;	//Avoid Duplicates			
    			int target=-num[i];
    			int j=i+1;			
    			int k=num.length-1;		
    			while (j<k){
    				if (j>i+1&&num[j]==num[j-1]){
    					j++;
    					continue;//Avoid Duplicates		
    				}
    				if (k<num.length-1&&num[k]==num[k+1]){
    					k--;
    					continue;//Avoid Duplicates		
    				}					
    				if ((num[j]+num[k])>target) 
    					k--;
    				else if ((num[j]+num[k])<target)
    					j++;
    				else
    					results.add(new ArrayList<Integer>(Arrays.asList(num[i],num[j++],num[k--])));				
    			}
    		}
    		return results;
    	}
    }

  • 0
    M

    This is quite bad. What is the reason to limit running time this aggressively? If N^2 is what you are looking for then let is pass!


Log in to reply
 

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