[python|파이썬] 세 수의 합 / 세수의 합이 0이 되는 경우

세 수의 합 3Sum

세 수의 합이 0이 되는 경우를 구하는 문제

 

💗브루트 포스로 계산하기

각 배열에서 나올 수 있는 모든 경우의 수를 계산하고 답을 도출하는 방법

리트코드에서 해당 방법으로 풀이하면 시간초과에러가 발생한다 😢

    result = []
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                if nums[i] + nums[j] + nums[k] == 0:
                    if sorted([nums[i],nums[j],nums[k]]) not in result:
                        result.append(sorted([nums[i],nums[j],nums[k]]))

    return result

 

💗투포인터로 계산하기

각 배열을 돌아가면서 나머지 두 수의 합이 -(해당 값)이 되는 경우를 찾는 방법

 

    result = []
    nums.sort()

    for i in range(len(nums)-2):
        # 중복 값이 없도록!
        if i>0 and nums[i] == nums[i-1]:
            continue

        left, right = i+1, len(nums)-1
        while left < right:
            sum = nums[i] + nums[left] + nums[right]
            if sum < 0:
                left += 1
            elif sum > 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 result

 

💗양수, 음수, 0으로 나눠서 계산하기

nums 배열 안에 있는 숫자들을 양수, 음수, 0으로 나눈 후, 각 경우에 해당하는 값이 배열에 존재하는 지 확인하는 방법

if len(nums) < 3:
    return []

res = set()

n, p, z = [], [], []
for num in nums:
    if num > 0:
        p.append(num)
    elif num < 0:
        n.append(num)
    else:
        z.append(num)

N, P = set(n), set(p)

if z:
    for num in P:
        if -1 * num in N:
            res.add((-1 * num, 0, num))

    if len(z) >= 3:
        res.add((0, 0, 0))

from itertools import combinations

for x, y in combinations(n, 2):
    target = -1 * (x + y)
    if target in P:
        res.add(tuple(sorted([x, y, target])))

for x, y in combinations(p, 2):
    target = -1 * (x + y)
    if target in N:
        res.add(tuple(sorted([x, y, target])))

return [list(x) for x in res]

 

https://leetcode.com/problems/3sum/submissions/670313789