Intuition

1차원 배열에서 두 원소의 합이 target이 될 때 두 원소의 인덱스 출력

Approach

배열의 길이가 길어서 시간복잡도를 $$ O(n^2) $$ 미만으로 작성해야 함 -> 두 원소 활용해서 무언가 해야하는 문제이므로 투포인터 활용하고. 그 전에 정렬먼저 시키기

Complexity

• Time complexity: $O(nlogn)$

  • sorted() 가 있어서 nlogn. 두 수 합 확인 부분은 n

• Space complexity: $O(n)$

  • 1차원 리스트 생성하므로 n

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sorted_nums = sorted(nums)
        s = 0
        e = len(nums)-1
        s_item = 0
        e_item = 0

        while s<e:
            if sorted_nums[s] + sorted_nums[e] < target:
                s += 1
            elif sorted_nums[s] + sorted_nums[e] > target:
                e -= 1
            else:
                s_item = sorted_nums[s]
                e_item = sorted_nums[e]
                break
        ans1 = nums.index(s_item)
        for i in range(len(nums)):
            if nums[i] == e_item and i != ans1:
                ans2 = i
                break

        return [ans1, ans2]