두 개의 합 문제

인기 있는 배열 문제는 두 개의 합 문제입니다. 문제는 주어진 배열에서 합이 목표 값과 같은 두 개의 숫자를 찾습니다. 다음을 사용하여 이 문제를 해결하는 몇 가지 방법이 있습니다.

순진한 접근 방식

두 포인터 기술

해시 맵

array = [1,2,3,4,5]
targetSum = 5

순진한 접근

이 기술에는 두 개의 for 루프를 사용하여 대상 합계를 찾기 위해 배열을 반복하는 작업이 포함됩니다. 이 방법의 시간 복잡도는 O(n^2)이고 공간 복잡도는 O(1)입니다.

def twoNumberSum(array, targetSum):
    for i in range(len(array)):
        for j in range(len(array)):
            if array[i] + array[j] == targetSum and array[i] != array[j]:
                return [array[i], array[j]]
    return []

twoNumberSum(array, targetSum)
[1, 4]

두 포인터 기술

이 기술에는 배열의 시작 부분과 끝 부분에 하나씩 두 개의 포인터가 포함됩니다. 두 포인터의 값이 대상보다 작으면 왼쪽 포인터를 오른쪽으로 이동하고 값이 더 크면 오른쪽 포인터를 왼쪽으로 이동합니다.

시간 복잡도는 O(nlog(n))이고 공간 복잡도는 O(1)입니다.

def pointerSum(arr, tar):
    l = 0
    r = len(arr) - 1
    while l < r:
        if arr[l] + arr[r] == tar:
            return [ arr[l], arr[r] ]
        if arr[l] + arr[r] < tar:
            l += 1
        if arr[l] + arr[r] > tar:
            r -= 1

    return []

pointerSum(array, targetSum)
[1, 4]

해시맵 기법

이 기술은 배열을 해시 맵에 저장한 다음 해시 맵의 상수 조회 기능을 사용하여 해당하는 두 합 수를 찾습니다.

def hashSum(arr, tar):
    hashmap = {}
    for i in range(len(arr)):
        hashmap[i] = arr[i]
        complement = tar - arr[i]
        if complement in hashmap.values() and complement != arr[i]:
            return [ arr[i], complement]
    return []

hashSum(array, targetSum)
[3, 2]