15. 3Sum

https://leetcode.com/problems/3sum/?envType=featured-list&envId=top-google-questions

input :

• nums

output :

• 3개의 원소를 더하였을 떄 0이 되는 원소들의 집합을 출력하시오.

조건 :

• 원소들은 중복되어 선택이 불가능하다. (i != j != k)
• 3 <= len(nums) <= 3000

---

Solution explain : Solution1

idea

• nums를 정렬하여 포인터가 이동될 때 마다 0을 기준으로 판단하자.
• i는 반복문의 시작점으로 고정 j, k는 i + 1, len(nums) - 1으로 설정.
• j를 키우면 0보다 커질 수 있고, k를 줄이면 0보다 작아질 수 있다.
• 모든 값들을 더해서 0과 비교한다.

주의

• set()을 통해 중복을 쉽게 제거 할 수 있다. 리스트의 in과 같은 키워드를 쓰기에는 연산량을 많이 잡아먹는다.

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ret = set()
        nums.sort()

        for i in range(len(nums)):
            j, k = i + 1, len(nums) - 1
            if j >= k:
                continue

            while j < k:
                val1, val2, val3 = nums[i], nums[j], nums[k]
                temp = val1 + val2 + val3
                if temp == 0:
                    ret.add((val1, val2, val3))
                    j += 1
                    k -= 1
                    continue

                if temp > 0:
                    k -= 1
                else:
                    j += 1

        return list(ret)

# s = Solution()
# print(s.threeSum([-1,0,1,2,-1,-4,-2,-3,3,0,4]))
# print(s.threeSum([-1,0,1,2,-1,-4]))
# print(s.threeSum([0,1,1]))
# print(s.threeSum([0,0,0]))