Two Pointer

정렬은 O(nlogn)

---

정수가 저장된 배열 nums이 주어졌을 떄, nums의 원소중 두 숫자를 더해서 target이 될수 있으면 True 불가능하면 False를 반환하세요.
같은 원소를 두 번 사용할 수 없습니다.

func twoPointer() -> Bool {
    var nums: [Int] = [4,1,9,7,5,3,16]
    let target = 14
    var l = 0
    var r = nums.count - 1

    //O(nlongn)
    nums.sort()

    //O(n)
    while l < r {
        if nums[l] + nums[r] > target {
            r -= 1
        } else if  nums[l] + nums[r] < target {
            l += 1
        } else  if nums[l] + nums[r] == target {
            print(nums[l], nums[r])
            return true
        }

    }

    return false

}



제약조건
2 <= nums.length <= 10^4                                     
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

---

• 정렬은 nlogn의 시간복잡도를 가지고 있고
• List는 Direct Acceess이므로 접근시 O(1)
• nums의 길이만큼 동작하기에 O(n), 빅오 표기법상 해당 코드의 시간복잡도는 O(nlogn)
• O(1) < O(n) < O(logn) < O(nlogn) < O(n²) < O(N!)