Leetcode Python - 15. 3Sum

Leetcode #15 - 3Sum

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 15 ‘3Sum’을 파이썬으로 풀어 보도록 하겠습니다.

time limit exceeded 에 걸리는 관계로.. discuss를 보도록 하겠습니다..

포인트는 어떻게 중복되는 값들을 제거하는가 인데, while구문을 이용해 더해나갔습니다.

전체 코드는 아래와 같습니다.

    res = []
    nums.sort()
    for i in range(len(nums)-2):
        if 0 < i and nums[i] == nums[i-1]:
            continue
        l, r = i+1, len(nums)-1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l +=1 
            elif s > 0:
                r -= 1
            else:
                res.append((nums[i], nums[l], nums[r]))
                while l < r and nums[l] == nums[l+1]:
                    l += 1
                while l < r and nums[r] == nums[r-1]:
                    r -= 1
                l += 1; r -= 1
    return res

시간복잡도는 O(n²) : for문과 그 안에 while문 공간복잡도는 O(1) : 상수 l,r,s 선언