My O(n^2) solution


  • 0
    L

    This is my code of solution. No hash was used. Only for and while loop.

    public List<List<Integer>> threeSum(int[] num) {
    	List<List<Integer>> list = new ArrayList<List<Integer>>();
    	List<Integer> n = new ArrayList<Integer>();
    	int count = 0;
    	
    	if(num.length<3) return list;
    
    	// Sort the array in an non-decreasing order
    	quickSort(num, 0, num.length-1);
    	
    	for(int i=1; i<num.length; i++) {
    		int left = i-1;
    		int right = i+1;
    		while(left >= 0 && right <= num.length-1) {
    			if(num[right]+num[left]+num[i] == 0) {
    				List<Integer> triplet = new ArrayList<Integer>();
    				triplet.add(num[left]);
    				triplet.add(num[i]);
    				triplet.add(num[right]);
    				list.add(triplet);
    				right++;
    				left--;
    			} else if (num[left]+num[right]+num[i]>0) {
    				left--;
    			} else {
    				right++;
    			}
    		}
    	}
    	
    	for(int i=0; i<list.size(); i++) {
    		for(int j=i+1; j<list.size(); j++) {
    			if(list.get(i).get(0)==list.get(j).get(0)
    					&&list.get(i).get(1)==list.get(j).get(1)
    					&&list.get(i).get(2)==list.get(j).get(2))
    				{
    					list.remove(j);
    					j--;
    				}
    		}
    	}
    	
    	return list;
    }

Log in to reply
 

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