23806: 三数之和

http://cs101.openjudge.cn/practice/23806/

给你一个包含 n 个整数的输入，判断其中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 的三元组的个数。注意：重复的三元组记作一个。暴力解会导致时间超时。

输入

n个整数，n<=3000

输出

满足条件的三元组的个数

样例输入

-1 0 1 2 -1 -4

样例输出

提示

满足条件的三元组分别是[-1,-1,2]和[-1,0,1]，共计2个

可以采用排序的方式解答

来源: 计算概论B 2021 期末考试

python

def threeSum(nums):
    nums.sort()  # 先对数组排序
    result = []
    n = len(nums)

    for i in range(n - 2):
        # 跳过重复的元素
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # 双指针
        left = i + 1
        right = n - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([nums[i], nums[left], nums[right]])

                # 跳过重复的元素
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1

                left += 1
                right -= 1

    return len(result)

*nums, = map(int, input().split())
#nums = [-1, 0, 1, 2, -1, -4]
count = threeSum(nums)
print(count)

python

"""
集合（set）可以自动去除重复的三元组，而查找的时间复杂度仍为O(1)，
并且空间复杂度也不会超过O(n)。
"""
def threeSum(nums):
    nums.sort()
    res = set()
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        d = {}
        for x in nums[i + 1:]:
            if x not in d:
                d[-nums[i] - x] = 1
            else:
                res.add((nums[i], -nums[i] - x, x))
    return len(res)

n = list(map(int, input().split()))
print(threeSum(n))

23806: 三数之和 ​

23806: 三数之和