python - 查找小于给定数字的三胞胎

Question

我正在尝试解决以下问题:

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, 0, 1, 3], and target = 2.

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

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

我的算法:从列表中删除单个元素，设置 target = target - number_1，搜索 number_1 + number _2 < target - number_1 的双元组。问题解决了。

问题链接是https://leetcode.com/problems/3sum-smaller/description/ .

我的解决方案是:

    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

我的解决方案通过了 30 多个测试用例，我不明白为什么会出现错误。

感谢您的帮助。

Answer 1

一个要点是，当您对第一行中的元素进行排序时，您也会丢失索引。这意味着，尽管找到了三元组，但您永远无法确定您的 (i, j, k) 是否正确。将满足条件 1，因为那些 (i, j, k)不是来自原始列表，而是来自新列表。

此外:每次从数组中间取出一个元素时，数组的剩余部分也会被迭代(尽管以不规则的方式，它仍然从 tmp 中剩余元素的第一个开始)。不应该这样!我正在扩展详细信息:

该示例在列表上迭代 3 次(再次排序，因此您丢失了真正的 i、j 和 k 索引):

• 第一次迭代(i = 0, tmp = [1, -2], t = 0)。 当你总结 temp[l] + temp[r] ( l, r 是 0, 1 )它将是 -1 . 满足低于t . smaller会增加。
• 第二次迭代将与第一次迭代类似，但使用 i = 1 . 它会再次增加。
• 第三个也会增加，因为t = 3总和将为 2现在。

因此，您将对值进行三次计数(尽管只能按索引顺序形成一个元组)，因为您正在遍历索引的排列而不是组合 其中。所以你没有关心的这两件事:

• 排序时保留索引。
• 确保您仅以前向方式迭代索引。

像这样更好地尝试:

def find(elements, upper_bound):
    result = 0
    for i in range(0, len(elements) - 2):
        upper_bound2 = upper_bound - elements[i]
        for j in range(i+1, len(elements) - 1):
            upper_bound3 = upper_bound2 - elements[j]
            for k in range(j+1, len(elements)):
                upper_bound4 = upper_bound3 - elements[k]
                if upper_bound4 > 0:
                    result += 1
    return result