leetcode: 1. Two Sum

문제링크

풀이1

• 모든 경우의 수 검사

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val results = IntArray(2)
        for (i in 0 until nums.size) {
            for (j in 0 until nums.size) {
                if (i != j && nums[i] + nums[j] == target) {
                    results[0] = i
                    results[1] = j
                    break
                }
            }
        }
        return results
    }
}

시간복잡도 : O(N^2)
공간복잡도 : O(N)

풀이2

• map의 key를 target에서 배열의 원소 값을 가지도록 하고, value를 인덱스로 가진다.
• map의 key 중 배열의 원소 값이 존재하면, 해당 인덱스들을 반환한다.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val results = IntArray(2)
        val numMap = hashMapOf<Int, Int>()
        for (i in 0 until nums.size) {
            if (nums[i] in numMap) {
                results[0] = i
                results[1] = numMap[nums[i]]!!
            } else {
                numMap[target - nums[i]] = i
            }
        }
        return results
    }
}

시간복잡도 : O(N)
공간복잡도 : O(N)

풀이3

• 풀이2의 방법과 자료구조를 제외하고 방법은 동일하다.
• map과는 달리 index를 저장하지 않기 때문에 index를 구하는 코드를 추가한다.

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val results = IntArray(2)
        var temp = 0
        val numSet = hashSetOf<Int>()
        for (i in 0 until nums.size) {
            if (nums[i] in numSet) {
                results[0] = i
                temp = target - nums[i]
                break
            } else {
                numSet.add(target - nums[i])
            }
        }
        for (i in 0 until nums.size) {
            if (temp == nums[i]) {
                results[1] = i
                break
            }
        }
        return results
    }
}

시간복잡도 : O(N)
공간복잡도 : O(N)