My java AC solution in O(n^2)


  • 0
    W
    public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> t = new ArrayList<List<Integer>>();
        if (nums.length < 3) {
            return t;
        }
        Arrays.sort(nums);
        int temp = 1;   
        for (int i = 0; i < nums.length - 2; i++) {
        	if (temp != nums[i]) {     
        		findTriplet(t, nums, i, -nums[i]);
        	}
            temp = nums[i];
        }
        return t;
    }
    
    public static void findTriplet(List<List<Integer>> t, int[] nums, int k, int sum) {
        int i = k + 1;
        int j = nums.length - 1;
        while (i < j) {
            if (nums[i] + nums[j] < sum) {
                i++;
            } else if (nums[i] + nums[j] > sum) {
                j--;
            } else {
            	if (t.size() > 0 && t.get(t.size() - 1).get(0) == nums[k] && t.get(t.size() - 1).get(1) == nums[i] 
            			&&t.get(t.size() - 1).get(2) == nums[j]) {
            		i++;
                    j--;
            		continue;
            	}
                List<Integer> list = new ArrayList<Integer>();
                list.add(nums[k]);
                list.add(nums[i]);
                list.add(nums[j]);
                t.add(list);
                i++;
                j--;
            }
        }
    }
    

    }


Log in to reply
 

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