Leetcode167.Two Sum II - Input Array Is Sorted

소스코드

문제

• 167. Two Sum II - Input Array Is Sorted
• numbers int array 가 주어지며, numbers 중 2개의 숫자를 더해 target 을 만족

풀이 (brute-force)

• 시간복잡도 O (n 제곱)

• for 2번 돌리면서 순회 target 보다 크면 stop

풀이(공간 사용)

• Map 에 저장을 한다
• for loop 순회하면서 target - numbers[i] = map 에 있는지 체크
• 이러면 시간복잡도 O(n), 공간복잡도 또한 O(n)

풀이 (two Pointer)

• 양끝에서 시작
• 양끝의 합이 target 보다 크면 right--
• 양끝의 합이 target 보다 작으면 left++
• 이렇게 진행하면 결국 원하는 값을 찾게됨
• 시간복잡도 O(n) / 공간복잡도 O(1)

소스

      /**
     * 1. 문제
     *  numbers 중 2개의 수를 더해 target 만족
     *
     * 제약조건
     * 공간복잡도 O(1)
     * numbers 중복허용
     * 2 <= numbers.length <= 3 * 104
     * -1000 <= numbers[i] <= 1000
     * numbers array asc
     * -1000 <= target <= 1000
     * 오직 1개의 solution 이 존재
     *
     *
     * 2. 풀이
     * 2.1 brute-force  (시간복잡도 O (n 제곱) )
     *  - for 2번 돌리면서 순회
     *  - target 보다 크면 stop
     *
     * 2.2 공간복잡도를 쓴다면
     *  Map 에 저장을 한다
     *  for loop 순회하면서 target - numbers[i] = map 에 있는지 체크
     *  이러면 시간복잡도 O(n)
     *
     * 2.3 two pointer
     *  양끝에서 시작
     *  양끝의 합이 target 보다 크면 right--
     *  양끝의 합이 target 보다 작으면 left++
     *
     *  시간복잡도 O(n) / 공간복잡도 O(1)
     */

    fun twoSumBruteForce(numbers: IntArray, target: Int): IntArray {
        for (i in 0 until numbers.size) {
            for (j in i + 1 until numbers.size) {
                if (numbers[i] + numbers[j] == target) {
                    return intArrayOf(i + 1, j + 1)
                }
            }
        }
        return intArrayOf()
    }

    fun twoSum(numbers: IntArray, target: Int): IntArray {
        var left = 0
        var right = numbers.size - 1

        // 무조건 답이 1개 있으니 true 로 해도 됨
        while (true) {
            val sum = numbers[left] + numbers[right]
            if (sum == target) {
                return intArrayOf(left + 1, right + 1)
            } else if (sum < target) {
                left++
            } else if (sum > target) {
                right--
            } else {
                // 이 경우는 없음
            }
        }
        return intArrayOf()
    }