[leetcode] 15. 3Sum 풀이, 해설 (python)

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

1차 풀이 

접근법을 못찾아서 O(n*n)으로 푸는 방법을 시도했다. 

a,b를 찾아서 -(a + b)값이 다른 배열안에 있는지 확인하는 방법이었다. 

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        dset = set()
        for num in nums:
            if num not in dset:
                dset.add(num)
        
        
        result = set()
            
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                check = nums[i] + nums[j] 
          
                if -check in dset and nums.index(-check) not in [i, j]:
                    # 중복값 체크 위해 정렬해서 키를 생성 
                    r = tuple(sorted([nums[i], nums[j], -check]))
                    result.add(r)
                
        
        return result

시간초과

 

2차 풀이 

이 시간초과를 해결하고자, 이미 확인한 값에 대해서는 넘어가는 로직을 추가했다. 

그러더니 시간초과는 해결이 되었다. 

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        dset = defaultdict(list)
        for i, num in enumerate(nums):
            dset[num].append(i)
        
        result = set()
            
        # 시간 줄이기 위해 체크한 값에 대해서 결과값 저장 
        checked = set()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                check = nums[i] + nums[j] 

                if (nums[i], nums[j]) in checked:
                   continue
        
                if -check in dset:
                    # i,j 조건 확인 
                    if dset[-check] == [i] or dset[-check] == [j] or dset[-check] == [i,j] or dset[-check] == [j, j]:
                        continue
                    
                    # 중복값 체크 위해 정렬해서 키를 생성 
                    r = tuple(sorted([nums[i], nums[j], -check]))
                    result.add(r)

                # 시간 초과 해결하기 위해 저장해둠 
                checked.add((nums[i], nums[j]))
                
        
        return result

 

해설

https://www.youtube.com/watch?v=jzZsG8n2R9A

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

 

 

 

 

참고로, 해설은 여기 방법과 유사한 접근으로 문제를 풀었다. 

https://ddoance.tistory.com/149

[leetcode] 167. Two Sum II - Input Array Is Sorted 풀이, 해설 (python)