3Sum Smaller


  • 0

    Click here to see the full article post


  • 0
    P

    Couldn't have been better.


  • 0
    A

    How does the 2 pointer method take care of duplicates?


  • 0
    C

    I have a question for the twoSumSmaller:

    private int twoSumSmaller(int[] nums, int startIndex, int target) {
        int sum = 0;
        for (int i = startIndex; i < nums.length - 1; i++) {
            int j = binarySearch(nums, i, target - nums[i]);
            sum += j - i;
        }
        return sum;
    }
    

    Why we use binary search for target - nums[i] from index i, rather than i+1? I think we need to find the right most position after i, then it is int j = binarySearch(nums, i+1, target - nums[i]);, but the answer is wrong. Thx!


  • 0
    C

    @anku There is no need to consider the duplicates of numbers , only index i, j, k are different is enough.


  • 0
    S

    Sorting array, rearranges the array, so not sure how is it solving original question of finding i,j,j in unsorted array.


  • 0
    S

    Can I know why "right - left" is added to sum? I wonder how does it count distinct pairs of numbers between "left" and "right" that add upto less than target?


Log in to reply
 

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