[리트코드/파이썬] 15. 3Sum(투 포인터)
난이도:
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]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
- 3 <= nums.length <= 3000
- 105 <= nums[i] <= 105
[내 풀이(1차)]
※ 풀이 전략
- 투 포인터, i는 첫 값 나머지 두 값은 투 포인터로 결정. 이 경우 i*j*k = n^3일 뻔 했던 것이 i*((j,k)) = n^2 가 되는 효과가 있다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 투 포인터 사용
result = []
nums.sort()
print(nums)
for i in range(len(nums)-2):
# 시작 i 중복 제거
if i>0 and nums[i] == nums[i-1]:
continue
# 간격 좁혀나가며 합을 계산 (투 포인터)
left, right = i+1, len(nums) -1
while left < right:
sum = 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
if sum < 0:
left += 1
elif sum > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
return result
예외케이스 :
[-2,1,1]에서 1, 1을 각각 left/right 이 가져갈 수 있는데,
while 문을 한꺼번에 중복 넘어가게 해버리면 이 경우 한 쪽 포인터가 모두 가져버리고 넘기는 문제 발생
[내 풀이(2차)]
※ 풀이 전략
- 위의 예외 케이스를 해결한 풀이, 정상적으로 통과
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 투 포인터 사용
result = []
nums.sort()
print(nums)
for i in range(len(nums) - 2):
# 시작 i 중복 제거
if i > 0 and nums[i] == nums[i - 1]:
continue
# 간격 좁혀나가며 합을 계산 (투 포인터)
left, right = i + 1, len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum < 0:
while left < right and nums[left] == nums[left + 1]: # 중복 값을 모두 넘어간 뒤 다음 값
left += 1
left += 1
elif sum > 0:
while left < right and nums[right] == nums[right - 1]: # 중복 값을 모두 넘어간 뒤 다음 값
right -= 1
right -= 1
else:
result.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 result
※ 중요 포인트
- 투 포인터를 사용하면 n을 한 단계 줄일 수 있다. O(n^3) -> O(n^2)
댓글