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?


  • 1
      def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        result = 0
        nums.sort()
        for i in range(len(nums) - 2):
          l, r = i + 1, len(nums) - 1
          while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < target:
              result += r - l
              l += 1
            else:
              r -= 1
        return result
    

Log in to reply
 

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