[Leetcode/Python] 15. 3sum

 

 

🤔 문제. 

Array에서 3개를 골라 0이 되는 sub-array를 구하는 문제입니다.

처음에는 2Sum을 구한 후에 하나씩 확인하며 구성하는 것으로 구현했는데, 시간초과가 나버렸습니다... 시간을 좀 더 들여 고민한 결과 정렬 후 투포인트로 문제를 풀었습니다. 

 

🤗 풀이. 

1. Array를 sort한다. 
2. for문을 통해 값을 하나 잡고, left/right 포지션을 지정한다.
3. 투포인트를 옮기면서 합이 0이되는 Array를 저장한다. 
   (이때 중요한 점은 정답에 같은 Array는 포함되지 않도록 함으로 같은 과정을 최소화하는 방향으로 진행한다.)

	class Solution:
	def threeSum(self, nums: List[int]) -> List[List[int]]:
	if len(nums) < 3: return [] # 0을 만들 수 없는 경우
	nums.sort()
	if nums[0] > 0 or nums[-1] < 0: return [] # 0을 만들 수 없는 경우
	ans = []
	for i in range(len(nums)-2):
	left, right = i+1, len(nums)-1
	if i > 0 and nums[i] == nums[i-1]: # 이전에 같은 수에 대해서 진행한 경우
	continue
	while left < right:
	sum3 = nums[i] + nums[left] + nums[right]
	if sum3 == 0:
	ans.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
	elif sum3 > 0:
	right -= 1
	else:
	left += 1
	return ans

view raw 3sum.py hosted with ❤ by GitHub

 

 

결과