Explanation of the algorithm with a simple Java O(n^2) solution


  • 0
    L

    O(n^3) is a straight-forward solution, albeit not optimal for this problem. Sorting should help you make the array look better for further optimization. Once you do that, it becomes a regular two-sum problem after that. So essentially:
    sorting : nlogn
    iteration: for each element , call twosum : n^2

    The slightly tricky part is to avoid the duplicates. Two tricky testcases are :

    1. // [-1, 0, 1, 2, -1, -4]
      You may have duplicate sets of -1. The best is to skip the second occurence since we have already built up the first set.

    2. //[-2,0,0,2,2]
      You should skip when the current lower and higher match with the next set since it may lead to the duplicate answer.

        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ll = new ArrayList<>();
    
            Arrays.sort(nums);
            for(int i=0;i<nums.length;i++) {
                if(i>0 && nums[i]==nums[i-1]) {
                    continue;
                }
                int first = 0 - nums[i];
                int s = i+1;
                int e = nums.length-1;
                while(s<e) {
                    if(nums[s]+nums[e]==first) {
                        ll.add(Arrays.asList(nums[i],nums[s],nums[e]));
                        s++;
                        e--;
                        while(s<e && nums[e]==nums[e+1] && nums[s]==nums[s-1]) {
                            e--;
                            s++;
                        }
                    }
                    else if(nums[s]+nums[e]>first) {
                        e--;
                    }
                    else {
                        s++;
                    }
                }
            }
            return ll;
        }
    

Log in to reply
 

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