[알고리즘 연습] 배열에서 타겟과 일치하는 수 2개 찾기

배열에서 타겟과 일치하는 수 2개 찾기

• int형 배열과 int형 타겟수이 주어진다.
• 배열에는 중복되는 수가 없다.
• 두 수를 합쳐서 타겟수이 되는 두 수가 반드시 배열에 존재한다.

---

풀이

def twoSum(nums, target):
    nums.sort()
    i = 0
    j = len(nums) - 1

    while i < j:
        sum = nums[i] + nums[j]
        if sum == target:
            return nums[i], nums[j]
        elif sum > target:
            j -= 1
        elif sum < target:
            i += 1
    return a,b

• sort를 진행해 배열을 순서대로 만든다. (시간복잡도 O(N logN))
• 그리고 양끝에 인덱스를 하나씩 두고 두 수의 합이 너무 크면 끝 인덱스를 줄이고, 두 수의 합이 너무 작으면 앞 인덱스를 늘리는 방식으로 진행한다.
• 여러 케이스를 생각하면 단순히 for문을 2번도는것보다 더 효율적이다.