259. 3Sum-Smaller.md

Description

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example:

Input: nums = [-2,0,1,3], and target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
             [-2,0,1]
             [-2,0,3]

Follow up: Could you solve it in O*(n^2) runtime?

---

暴破 + 剪枝，没想到通过了……

python solution

class Solution:
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        cnt = 0
        nums.sort()
        for i in range(len(nums) - 2):
            if 3 * nums[i] > target:
                break
            for j in range(i + 1, len(nums) - 1):
                if nums[i] + 2 * nums[j] > target:
                    break
                for k in range(j + 1, len(nums)):
                    if nums[i] + nums[j] + nums[k] < target:
                        cnt += 1
                    else:
                        break
        return cnt


print(Solution().threeSumSmaller(nums=[-2, 0, 1, 3], target=2))

贴上别人O(n^2)的解法, 使用双指针，的确巧妙！

# O(n*n) time
def threeSumSmaller(self, nums, target):
    count = 0
    nums.sort()
    for i in range(len(nums)):
        j, k = i+1, len(nums)-1
        while j < k:
            s = nums[i] + nums[j] + nums[k]
            if s < target:
                # if (i,j,k) works, then (i,j,k), (i,j,k-1),...,
                # (i,j,j+1) all work, totally (k-j) triplets
                count += k-j
                j += 1
            else:
                k -= 1
    return count