0259._3Sum_Smaller.md

259. 3Sum Smaller

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/3sum-smaller/

内容描述

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(n2) runtime?

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

3sum的思想, beats 33.02%

class Solution(object):
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        n, res = len(nums), 0
        nums.sort()
        for i in range(n):
            l, r = i+1, n-1
            while l < r:
                tmp = nums[i] + nums[l] + nums[r]
                if tmp < target:
                    res += r-l
                    l += 1
                elif tmp >= target:
                    r -= 1
        return res