Leetcode #1 Two Sum

문제

two_sum함수에 숫자 리스트와 '특정 수'를 인자로 넘기면, 더해서 '특정 수'가 나오는 index를 배열에 담아 return해 주세요.

nums: 숫자 배열
target: 두 수를 더해서 나올 수 있는 합계
return: 두 수의 index를 가진 숫자 배열

예를 들어,

nums은 [4, 9, 11, 14]
target은 13 

nums[0] + nums[1] = 4 + 9 = 13 이죠?

그러면 [0, 1]이 return 되어야 합니다.

가정

target으로 보내는 합계의 조합은 배열 전체 중에 2개 밖에 없다고 가정하겠습니다.

나의 정답

def two_sum(nums, target):
  result = []
  
  for a in range(0,len(nums)):
    for b in range(0,len(nums)):
      if nums[a] + nums[b] ==target:
        result = [a,b]
       
        return result

• 빈 리스트 result 선언
• 파라미터로 들어온 리스트 nums를 전부 슬라이싱하여 만족하는 target값이 존재할 경우 result값에 저장 후 반환
• for문을 2번 사용하게 되어 시간복잡도가 $O(n^2)$가 되버림
• for문을 한번으로 줄이는 것으로 수정이 필요

수정

def two_sum(nums, target):
  result = []

  for i in nums:
    if target - i in nums:
      a = nums.index(i)
      b = nums.index(target-i)
      result.append(a)
      result.append(b)
      
      return result

• target = nums 안의 element 2개의 합(a+b)인 것을 이용
• index()를 이용하여 순서를 찾아 result에 저장후 반환
• if문을 이용하여 for문 중첩을 수정함