3Sum Smaller

  • 0

    Click here to see the full article post

  • 0

    Couldn't have been better.

  • 0

    How does the 2 pointer method take care of duplicates?

  • 0

    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

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

  • 0

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

  • 0

    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
        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
              r -= 1
        return result

Log in to reply

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