1. 투썸 - 리트코드 이지

문제 설명

정수 nums의 배열과 정수 target이 주어지면 두 숫자의 인덱스를 반환하여 합계가 target이 되도록 합니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다.

어떤 순서로든 답변을 반환할 수 있습니다.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

접근법 1

배열을 반복하면서 각 요소를 선택하고 첫 번째 배열에 추가될 때 대상 값을 제공하는 나머지 배열에 다른 요소가 있는지 확인합니다. 그러한 쌍이 하나 존재한다는 것이 보장됩니다. 따라서 인덱스를 반환해야 합니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]

        return [-1, -1]

시간 복잡도 - O(n^2) - 중첩된 for 루프 때문입니다.
공간 복잡성 - O(1) .

접근법 2

배열을 반복하고 대상에 합산하는 데 필요한 숫자가 해시맵에 이미 있는 경우 각 요소를 확인합니다. 하나가 있으면 두 인덱스가 모두 포함된 배열을 반환합니다. 그렇지 않으면 인덱스를 값으로, 항목을 키로 사용하여 현재 항목을 해시맵에 추가합니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashMap = {}
        for i in range(len(nums)):
            if target - nums[i] in hashMap: # If present in hashmap
                return [hashMap[target-nums[i]], i]
            else:
                hashMap[nums[i]] = i # Add item as key and index as value into hashmap

        return [-1, -1]

결론

다른 접근 방식을 놓친 경우 알려주십시오.

더 많은 설명을 위해 나를 따르십시오.
연결합시다: Showwcase