Java O(n^2) solution


  • 0
    M
    public class Solution {
        public List<List<Integer>> threeSum(int[] num) {
            if(nums==null) return null;
            Arrays.sort(num);
            List<List<Integer>> res = new ArrayList<>(); 
            for (int i = 0; i < num.length-2; i++) {
                if(i==0 || (i>0 && num[i]!=num[i-1])){ // remove duplicate
                    int left = i+1, right = num.length-1;
                    while(left<right){
                        int sum = num[i] + num[left] + num[right];
                        if(sum<0){
                            while(left<right && num[left]==num[left+1]) left++; // remove duplicate
                            left++;
                        } else if(sum>0){
                            while(left<right && num[right]==num[right-1]) right--; // remove duplicate
                            right--;
                        } else {
                            res.add(Arrays.asList(num[i], num[left], num[right]));
                            while(left<right && num[left]==num[left+1]) left++; // remove duplicate
                            while(left<right && num[right]==num[right-1]) right--; // remove duplicate
                            left++;
                            right--;
                        }
                    }
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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