Please I am just curious if there is a better way I can achieve the Leetcode ThreeSum problem.

I came up with this piece of code using Binary Search

    // Time Complexity: O(nlogn)   O(nlogn) == O(nlogn)
    // Extra Space Complexity: O(1)
    public static List<List<Integer>> threeSumOptimalSolution(int[] nums) {
        int n = nums.length;
        if (n < 3)
            return Collections.emptyList();
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int left;
        int right;
        int mid;
        int threeSum;
        for (int firstValue = 0; firstValue < n - 2; firstValue  ) {
            if (firstValue == 0 || nums[firstValue] != nums[firstValue - 1]) {
                left = firstValue   1;
                right = n - 1;
                while (left < right) {
                    mid = left   (right - left) / 2;
                    threeSum = nums[firstValue]   nums[left]   nums[right];
                    if (threeSum < 0) {
                        if (nums[mid]   nums[right]   nums[firstValue] < 0)
                            left = mid   1;
                        else
                            left  ;
                    } else if (threeSum > 0) {
                        if (nums[mid]   nums[left]   nums[firstValue] > 0)
                            right = mid - 1;
                        else
                            right--;
                    } else {
                        result.add(List.of(nums[firstValue], nums[left], nums[right]));
                        left  ;

                        while (nums[left] == nums[left - 1] && left < right)
                            left  ;

                        while (nums[right] == nums[right - 1] && left < right)
                            right--;
                    }
                }
            }
        }
        return result;
    }

I would appreciate an extensive review from individual/individuals.

CodePudding user response：

The best time complexity in the ThreeNums problem I know is O(n^2) And I think you want to use Two Pointers to finish the problem. In your Answer, the part Of Binary Search is wrong, I don't know what's are you doing. The correct method is to traverse the list outside and use Two Pointers inside. E.g

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i  ) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int left = i 1;
            int right = nums.length-1;
            while(left < right) {
                int sum = nums[i]   nums[left]   nums[right];
                if(sum == 0) { 
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    res.add(temp);
                    while(right > left && nums[right] == nums[right-1]) right--;
                    while(right > left && nums[left] == nums[left 1]) left  ;
                    right--;
                    left  ;
                } else if(sum > 0) {
                    right--;
                } else {
                    left  ;
                }
            }
        }
        return res;
    }
}