时间戳

首页 > 解决方案 > 3sum算法。我没有得到小于目标的数字的结果

python - 3sum算法。我没有得到小于目标的数字的结果

问题描述

我怎样才能让它打印总和小于或等于目标的所有三元组？目前，这会返回对目标的 = 的三元组。我试图改变和思考，但无法弄清楚

def triplets(nums):
    # Sort array first
    nums.sort()
    output = []

    # We use -2 because at this point the left and right pointers will be at same index
    # For example [1,2,3,4,5] current index is 4 and left and right pointer will be at 5, so we know we cant have a triplet
    #       _ LR
    for i in range(len(nums) - 2):

        # check if current index and index -1 are same if same continue because we need distinct results
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left < right:

            currentSum = nums[i] + nums[left] + nums[right]

            if currentSum <= 8:
                output.append([nums[i], nums[left], nums[right]])
                # below checks again to make sure index isnt same with adjacent index
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                # In this case we have to change both pointers since we found a solution
                left += 1
                right -= 1
            elif currentSum > 8:
                left += 1

            else:
                right -= 1

        return output

所以例如输入数组是[1,2,3,4,5]我们将得到结果 (1,2,3),(1,2,4),(1,2,5),(1,3,4) 因为这些总和小于或等于目标 8。

标签： pythonarrayswhile-loopreturnconditional-statements

解决方案

为解决新问题而对代码进行微小更改的主要障碍是，您sum == target可以O(n^2)使用两个循环及时解决输出所有不同三元组的原始目标，就像在您的算法中一样。输出的大小可以与 成比例n^2，因此在某种意义上这是最佳的。

输出具有 , 的所有不同三元组的问题sum <= target总是不能及时解决O(n^2)，因为输出的大小可能与n^3; 例如，对于数组nums = [1,2,...,n], target = n^2 + 1，答案是所有可能的三元组元素。因此，您的算法必须以相当于添加第三个循环的方式进行更改。

一种O(n^3)解决方案如下所示。在过滤重复元素方面更加聪明（例如使用哈希图和使用频率），这应该可以改进到输出的大小在O(max(n^2, H))哪里。H

def triplets(nums, target=8):
    nums.sort()
    output = set()

    for i, first in enumerate(nums[:-2]):

        if first * 3 > target:
            break

        # Filter some distinct results
        if i + 3 < len(nums) and first == nums[i + 3]:
            continue

        for j, second in enumerate(nums[i + 1:], i + 1):
            if first + 2 * second > target:
                break
            if j + 2 < len(nums) and second == nums[j + 2]:
                continue

            for k, third in enumerate(nums[j + 1:], j + 1):
                if first + second + third > target:
                    break
                if k + 1 < len(nums) and third == nums[k + 1]:
                    continue

                output.add((first, second, third))

    return list(map(list, output))

推荐阅读