【python-leetcode259-双指针】三个数的最小和

Example:

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.

For example,given nums = [-2,1,3],and target = 2.

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

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

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

class Solution(object):
    def threeSumSmaller(self,nums: List[int],target: int) -> int:    
        #如果nums为空或者长度小于3，直接返回0
        if not nums and len(nums) < 3:
            return 0
        先排序    
        nums.sort()
        如果前三个数的和都大于或等于target，直接返回0
        if nums[0]+nums[1]+nums[2]>=target:
            保存结果
        res =从左到右依次遍历
        for i in range(0,len(nums)):
            左指针和右指针
            l,r = i + 1,len(nums) - 1
            循环条件，核心就是下标为i的数为核心
            逐渐增大左指针指向的值，减小右指针指向的值，以匹配所有情况
            while l < r:
                如果当前三个值和小于target，此时说明以i,l~r之间组成都可以，比如[-2,target=2
                [-2,3]是可行的，那么左指针不变，右指针一直左移，这时都是符合条件的
                if nums[i] + nums[l] + nums[r] < target:
                    res += r - l
                    再让左指针右移，判断下一种情况
                    l += 1
                else:
                    如果当前三个数值大于或等于target，需要让右指针左移使值变小些
                    r -= 1
    return res