Three Sum solution in Java with O(N^2) time complexity


  • 4
    H
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            if(nums == null || nums.length < 3)
                return new LinkedList<>();
            List<List<Integer>> solutions = new LinkedList<>();
            Set<List<Integer>> temp = new HashSet<>();
            Arrays.sort(nums);
            for(int i = 0; i < nums.length - 2; i++){
                int j = i+1;
                int k = nums.length-1;
                while (j < k){
                    int sum = nums[i] + nums[j] + nums[k];
                    if(sum == 0){
                        List<Integer> solution = new LinkedList<>();
                        solution.add(nums[i]);
                        solution.add(nums[j]);
                        solution.add(nums[k]);
                        temp.add(solution);
                        j++;
                    }else if(sum > 0){
                        k--;
                    }else
                        j++;
                }
            }
            solutions.addAll(temp);
            return solutions;
        }
    }
    

Log in to reply
 

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