找到小于给定数字的三胞胎-Java 学习之路

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

给定n个整数nums和目标的数组，找到索引三元组i，j，k的数量，其中0 <= i <j <k <n满足条件nums [i] nums [j] nums [k] <目标 . 例如，给定nums = [-2,0,1,3]和target = 2.返回2.因为有两个三元组，其和小于2：[ - 2，0,1] [-2,0 ，3]

我的算法：从列表中删除单个元素，设置target = target - number_1，搜索doublets，使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多个测试用例 .

谢谢你的帮助 .

3 回答

2
一个要点是，当您对第一行中的元素进行排序时，您也会丢失索引 . 这意味着，尽管找到了三元组，但您永远无法确定 (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
```
回复于 2024-05-01T04:08:33+08:00
1

好像你不止一次计算同一个三元组......

在循环的第一次迭代中，省略列表中的第一个 1 ，然后通过 1 增加 smaller . 然后省略列表中的第二个 1 并再次 1 增加 smaller . 最后你省略了列表中的第三个元素 -2 ，当然还有 1 增加了 smaller ，因为 - 好 - 在所有这三种情况下你实际上都在考虑 same triplet {1,1,-2} .

附：看起来你更关心正确性而不是表现 . 在这种情况下，请考虑维护一组解决方案三元组，以确保您不会计算两次相同的三元组 .

回复于 2024-05-01T04:08:33+08:00

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

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)))

输出：

回复于 2024-05-01T04:08:33+08:00

找到小于给定数字的三胞胎

3 回答

相关问题