[Algorithm] Two Sum (python)

https://leetcode.com/problems/two-sum/

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                return True
    return False

print(twoSum(nums=[4,1,9,7,5,3,16], target=14))

• 직관적으로 떠올린 풀이
  • 전체를 훑어보며 조건과 일치하는지 탐색
  • o(n^2)

def twoSum(nums, target):
    nums.sort()
    l, r = 0, len(nums)-1

    while l < r:
        if nums[l] + nums[r] > target:
            r -= 1
        elif nums[l] + nums[r] < target:
            l += 1
        else:
            return True
    return False

print(twoSum(nums=[4,1,9,7,5,3,16], target=14))

• 다른 풀이
  • 정렬, two pointer 알고리즘 활용
    • 무작위 리스트를 정렬 -> two pointer로 해결
  • o(n log n)
    • 파이썬에서 구현한 정렬