259.3Sum Smaller

Tags: [sort], [two_pointer], [trick]

Com: {g}

Link: https://leetcode.com/problems/3sum-smaller/\#/description

Given an array ofnintegersnumsand atarget, find the number of index tripletsi, j, kwith0 <= i < j < k < nthat satisfy the conditionnums[i] + nums[j] + nums[k] < target.

For example, givennums=[-2, 0, 1, 3], andtarget= 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it inO(n2) runtime?

Solution: Sort, Two Pointer

class Solution(object):
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return 0

        # The reason why we can sort the array:
        # think about that we just focus on seeking the elements of tripplets,
        # we can sort the nums first, then once we find the tripplets, 
        # we can recovery the elements original order.
        # But this problem is only interested in the num of tripplets,
        # so we don't need to recovery the order of elements in each tripplet.
        nums.sort()
        counter = 0
        for i in xrange(len(nums) - 2):
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] < target:
                    counter += right - left
                    left += 1
                else:
                    right -= 1

        return counter

Revelation:

• The reason why we can sort the array has been commented in the code.
• counter += right - left, because we have already sort the array, all elements at the left side of nums[right] is less than or equal to nums[right], so the once we find the nums[i] + num[left] + nums[right] < target, the elements in index[left + 1, right - 1] can also satisfy the condition, so we don't need to move right to left side one by one.

Note:

• Time complexity = O(n^2), n is the number of elements of the given nums.