Java solution, beats 85.5% O(n2)


  • 0
    J
    public class Solution {
            public List<List<Integer>> threeSum(int[] num) {
            List<List<Integer>> res = new LinkedList<>(); 
            // we sort the arrays O(n log(n));
            Arrays.sort(num);
            // We compute in O(n)
            for(int i = 0; i < num.length ;i++) {
                if(i > 0 && num[i-1] == num[i]) continue;
                int j = i+1, k = num.length-1;
                while(j < k) {
                    if(num[j]+num[k]+num[i] == 0) {
                        res.add(Arrays.asList(num[i], num[j], num[k]));
                        while (j < k && num[j] == num[j+1]) j++;
                        while (j < k && num[k] == num[k-1]) k--;
                        j++; k--;
                    }
                    // We shift the two pointer until we have a new == 0, we stop if j==k
                    while(j < k && (num[j]+num[k]+num[i] < 0)) j++; 
                    while(j < k && (num[j]+num[k]+num[i] > 0)) k--;
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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