找出小于给定数的三胞胎

Question

给定一个由n个整数组成的数组nums和一个目标，求出满足nums[i]+nums[j]+nums[k]

例如，给定nums=[-2,0,1,3]，target=2。

返回2。因为有两个和小于2的三胞胎：

    def threeSumSmaller(nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        nums = sorted(nums) 
        smaller = 0

        for i in range(len(nums)):

            # Create temp array excluding a number

            if i!=len(nums)-1:
                temp = nums[:i] + nums[i+1:]

            else:
                temp = nums[:len(nums)-1]


            # Sort the temp array and set new target to target - the excluded number

            l, r = 0, len(temp) -1 
            t = target - nums[i]

            while(l<r):

                if temp[l] + temp[r] >= t:

                    r = r - 1

                else:

                    smaller += 1

                    l = l + 1


        return smaller

Input:
[1,1,-2]
1
Output:
3
Expected:
1

Answer 1

已经有了很好的答案，除此之外，如果你想检查你的算法结果，那么你可以利用这个内置的功能：

import itertools

def find_(vector_,target):
    result=[]
    for i in itertools.combinations(vector_, r=3):
        if sum(i)<target:
            result.append(i)
    return result

产出：

print(find_([-2, 0, 1, 3],2)) 

产出：

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

print(len(find_([-2, 0, 1, 3],2)))

2