문제 링크 : leetcode.com/problems/3sum/submissions/
3Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
제공되는 배열의 수 중 3개를 골라 0이 되는 수의 조합을 return 한다.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
for i in range(0, len(nums) - 2):
left = i + 1
right = len(nums) - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum == 0:
if not [nums[i], nums[left], nums[right]] in result:
result.append([nums[i], nums[left], nums[right]])
left += 1
elif sum < 0:
left += 1
else:
right -= 1
return result
투 포인터를 이용하는 방법으로 풀었다. 이 투 포인터를 이용하는 방법 굉장히 유용하다. 순차적인 1차원 배열에서 순환하며 무언가를 얻어내야 할 때 굉장히 좋다.
일단, 투 포인터를 쓰기 위해 정렬을 해서 순차적으로 만든다. 첫번째 수는 for문을 그대로 따라가고 포인터 하나는 첫번째 수의 오른쪽부터 끝방향으로, 포인터 두번째는 끝에서 첫번째 수 방향으로 이동한다. 세 수를 더해서 작으면 첫번째 포인터를 오른쪽으로 이동 크면 두번째 포인터를 왼쪽으로 이동시켜서 만날때까지 반복한다.
여기까지가 내가 이해한 내용.
책 보니깐 중복된 값 스킵하는 것과 포인터들을 이동시킬때 값이 같으면 스킵하고 또 이동시키는 부분이 빠졌다. 거기에 합이 0일 때 포인터 하나만 이동했는데 둘 다 이동시켜도 됐다.
나보다 느린 사람이 5%인거보니 정말 간당간당하게 통과했나보다...
부족한 부분을 적었더니 오류가 생긴다. 책 그대로 하면 정상동작한다;;;;;