[정렬] - 두수의 합

두 수의 합

정수 수열 안에서 수열의 원소 두 개의 합이 target값이 되는 경우를 찾고 싶습니다.
매개변수 nums에 길이가 n인 수열이 주어지고, 매개변수 target에 자연수 값이 주어지면 이 수열안에서 두 개의 원소의 합이 정수 target값이 되는 두 원소를 구해 배열에 오름차순으로 담아 반환합니다.
두 개의 원소의 합이 target값이 되는 경우는 오직 한가지 뿐인 입력만 주어집니다. 한 원소를 두 번 더하는 것은 안됩니다. nums의 각 원소는 유일값입니다.
답이 없을 경우 [0, 0]을 반환합니다.

제한사항:
• nums의 길이 3 <= n <= 200,000
• 배열 nums의 원소는 정수입니다. -10,000 <= nums[i] <= 10,000

• -20,000 <= target <= 20,000

 

나의 코드 

 

흠. 도저히 O(n^2) 이하의 시간복잡도를 가진 로직이 떠오르지 않는다..

투포인터를 생각해보았지만..흠 로직이 너무 복잡해지면서 결국 O(n^2)가 되게 되고..

슬라이드도 생각해 보았는데 흠..

모르겠다...

 

 

정답 코드

def solution(nums, target):
    answer = [0]*2
    nums.sort()
    left = 0
    right = len(nums) - 1
    while left < right:
        sumN = nums[left] + nums[right]
        if sumN == target:
            return [nums[left], nums[right]]
        if sumN < target:
            left += 1
        else:
            right -= 1
            
    return answer
    
                                        
print(solution([3, 7, 2, 12, 9, 15, 8, 11], 12))
print(solution([21, 12, 30, 15, 6, 2, 9, 19, 14], 24))
print(solution([12, 18, 5, 8, 21, 27, 22, 25, 16, 2], 28))
print(solution([11, 17, 6, 8, 21, 9, 19, 12, 25, 16, 2], 26))
print(solution([7, 5, 12, -9, -12, 22, -30, -35, -21], -14))
print(solution([7, 5, 12, 20], 15))

 

아...........

양끝 투포인터 생각 했었는데...

left가 오른쪽으로 이동하나 right가 왼쪽으로 이동하는게 도찐개찐이라고 오해했었다......꾸엑

흠.. 

📝 두수의 합은 정렬 후 양끝 투포인터 사용