파이썬 실습 23: 두 개의 합

의문

정수 배열nums 및 정수 배열target이 주어지면

은 두 숫자의 색인을 반환하여 합이 target가 되도록 합니다.

각 입력에는 정확히 하나의 솔루션이 있다고 가정할 수 있습니다.

동일한 요소를 두 번 사용할 수 없습니다.

원하는 순서로 답을 반환할 수 있습니다.

예시

예 1:

입력: 숫자 = [2,7,11,15], 대상 = 9
출력: [0,1]
설명: nums[0] + nums[1] == 9이므로 [0, 1]을 반환합니다.

예 2:

입력: 숫자 = [3,2,4], 대상 = 6
출력: [1,2]

예 3:

입력: 숫자 = [3,3], 대상 = 6
출력: [0,1]

제약:

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

하나의 유효한 답변만 존재합니다.

내 시도

첫번째 시도

알고리즘이 이론적으로 작동하지만 너무 느리고 마지막 두 테스트 케이스의 경우 시간이 부족합니다

.

알고리즘

> find the indices of the two number such that they add up to target
>>find two number if they add up to the target
  for index1, num1 in the nums:
      for index2,num2 in the nums:
          if num2 is not the same number as num1:
              if value1 + value 2 == target:
                  return a list consist of index1 and index2

코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        final_list = [[index1,index2] for index1,value1 in enumerate(nums) for index2,value2 in enumerate(nums) if index2 > index1 if value1+value2 ==target]
        return final_list[0]

두 번째 시도(모든 테스트 통과 성공)

알고리즘

> find the indices of the two number such that they add up to target
>>find two number if they add up to the target
  for index1,value1 in nums:
      calculate a second_number that have a sum with value equals to target
      if second is in nums:
          find the indices of the second_number
          if the second_number is not the same number as value1:
              return a list consist of index1 and index2

코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for index1, value1 in enumerate(nums):
            second_number = target - value1
            if second_number in nums:
                second_number_index = nums.index(second_number)
                if second_number_index != index1:
                    return [index1, second_number_index]

기타 솔루션

복잡도가 0(n)인 가장 빠른 알고리즘이라고 주장

알고리즘

> find the indices of the two number such that they add up to target
 initiate seen as empty dictionary
 for index, value in nums:
     calculate a second_number that have a sum with value equals to target
     if second_number is in seen dictionary:
         return a list of index and the index of second_number
     if second_number is not in seen:
         add the value as key and index as value in the seen dictionary

코드

class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       seen = {}
       for index, value in enumerate(nums):
           second_number = target - value

           if remaining in seen:
               return [index, seen[second_number]]

           seen[value] = index

내 반성

이것은 for 루프에만 완전히 의존하지 않는 방법을 생각하게 만드는 좋은 도전입니다. 그리고 검색 시간을 줄이기 위해 사전을 사용하는 새로운 패턴을 남들에게서 배운다.

신용 거래

에 도전 leetcode 1
솔루션 사용code recipe