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

概述问题描述： Example: Given an array of n integers nums and a target, find the number of index triplets i,

问题描述：

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

输入：[-2,3] 　　输出：2

是一道会员题，提交不了。

总结

以上是内存溢出为你收集整理的【python-leetcode259-双指针】三个数的最小和全部内容，希望文章能够帮你解决【python-leetcode259-双指针】三个数的最小和所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。