20240114 TIL

LeetCode 15. 3Sum

3Sum - LeetCode

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.



Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [0,1,1] Output: [] 
Example 3:
Input: nums = [0,0,0] Output: [[0,0,0]] 

나의 풀이

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        answer = [];
        n = len(nums) - 1;
        for i in range(n):
            a = 1
            for j in range(n-i):
                num = -(nums[i] + nums[i + a])
                if num in nums and nums.index(num) != i and nums.index(num) != i + a  : 
                    item = sorted([nums[i], nums[i + a], -(nums[i] + nums[i + a])])
                    if item not in answer:
                        answer.append(item)
                a = a + 1;
        return answer

시간복잡도에서 터짐 
아무리 안쪽에서 정리해봐도 이중 for 구문에서 터지는 것 같음

두 포인터를 활용한 풀이

class Solution(object):
    def threeSum(self, nums):
        answer = []
        nums.sort()

        for i in range(len(nums) - 2):
            left = i + 1, 
			right = len(nums) - 1
            
			#그 전에 체크했던 i 랑 같으면 넘어가기
            if i > 0 and nums[i] == nums[i - 1]:
                continue
						
            while left < right:
                sum = nums[i] + nums[left] + nums[right]

                if sum > 0:
                    right -= 1
                elif sum < 0:
                    left += 1
                else:
                    answer.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 answer

sum = for문으로 선택된 값 + left번째의 값 + right번째 값 이라고 한다면
sum > 0 이면 right -= 1
sum < 0 이면 left += 1
sum == 0 이면 answer에 추가한다.

이중 for 구문을 사용하면 리스트의 첫번째부터 마지막까지 다 확인하면서 결과값을 찾아야 하지만 포인터를 사용하면 더 적은 비용으로 모든 결과값을 찾을 수 있게 된다.