[LeetCode] 15. 3Sum [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀
문제 👉 <3Sum - LeetCode>

1. 문제 (세 수의 합)

배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라.

(중복된 엘리먼트 조합은 제외!!)

2. 풀이

• 투 포인터를 이용한 풀이

(출처)

1. 오름차순으로 정렬
2. for문을 통해 (해당 value, 다음 value, 마지막 value) 3개의 합을 계산한다.
   1. 합이 0보다 크면 다음 value를 오른쪽으로 한칸 이동
   2. 합이 0보다 작으면 마지막 value를 왼쪽으로 한칸 이동
   3. value가 이전값과 중복될 경우 continue

3. 코드

• 투 포인터를 이용한 풀이

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ret = []
        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:
                val = nums[i] + nums[left] + nums[right]
                if val > 0:
                    right -= 1
                elif val < 0:
                    left += 1
                else:
                    ret.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 ret

• 결과 :

방식	Status	Runtime	Memory	Language
투 포인터	[Accepted]	836 ms	17.6 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋