[LeetCode] 1. Two Sum

문제 링크 

https://leetcode.com/problems/two-sum/description/

Intuition

• 주어진 array의 element 중에 target 값으로 합의 수가 맞는 조합을 찾아야 하면..모든 element를 합해서 확인해 보자
• first + second index element의 합을 확인하고 넘어가야 한다 

Approach

• 당장 생각나는건...outer loop에서는 index 0 부터 좌항에 들어가는 인자를 iterate하고 inner loop에서는 우항에 들어가는 인자를 iterate 해서 둘의 합을 확인하는 방법 

Complexity

Time complexity:

• O(N^2) 

Space complexity:

Code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        done = False  
        for ptr1, i in enumerate(nums):
            ptr2 = ptr1 + 1
            while ptr2 < len(nums):
                if (nums[ptr1] + nums[ptr2] == target):
                    done = True 
                    break
                else: 
                    ptr2 += 1
            if (done):
                break

        return [ptr1, ptr2]

그런데 O(N^2) 풀이 보다 더 좋은 방법 없을까?