LeetCode15 - 3Sum

LC15 - 3Sum

Brute Force

3개의 element를 출력하는 문제이기 때문에 brute force를 이용하면 O(n^3)에 가능해 보인다. 즉 타임아웃이 발생할 것이다.

sort()함수를 통해 정렬 후 푼다면 간소화될 것이다. 정렬의 시간 복잡도는 O(n log n)이다.

brute force 풀이에 중복된 값이 있을 경우 무시하기 위해 continue 문을 적어준다.

if i > 0 and nums[i] == nums[i-1]:
    continue

# time limit exceeded
class Solution:
    def threeSum(self, nums):
        results = []
        nums.sort()
        
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums) - 1):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                for k in range(j + 1, len(nums)):
                    if k > j + 1 and nums[k] == nums[k - 1]:
                        continue
                    if nums[i] + nums[j] + nums[k] == 0:
                        results.append((nums[i], nums[j], nums[k]))
        return results

틀린 부분은 없지만 time limit exceeded

Two Pointer

기준점 i와 투 포인터를 이용하여 판별할 수 있다. 투 포인터가 간격을 좁혀나가며 sum을 계산한다.

left, right = i + 1, len(nums) - 1
while left < right:
    sum = nums[i] + nums[left] + nums[right

class Solution:
    def threeSum(self, nums):
        results = []
        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:
                    results.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 results