[LeetCode/C#] Two Sum

문제 출처 : https://leetcode.com/problems/two-sum/description/

 

 

[문제]

해당 문제는 주어진 배열 nums 와 정수 target 이 있을 때, 두 숫자의 합이 target 이 되는 배열의 인덱스를 반환하는 문제입니다.

 

[조건]

(1) 입력에는 반드시 하나의 정답만 존재합니다.

(2) 같은 원소를 두 번 사용할 수 없습니다.

(3) 반드시 하나의 정답이 존재합니다.

 

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        // Dictionary를 사용하여 숫자 값과 해당 인덱스를 저장
        Dictionary<int, int> numMap = new Dictionary<int, int>();

        // nums 배열을 순회
        for (int i = 0; i < nums.Length; i++) {
            // 현재 숫자(nums[i])의 보완 숫자(complement) 계산
            int complement = target - nums[i];

            // 보완 숫자가 Dictionary에 있는지 확인
            if (numMap.ContainsKey(complement)) {
                // 존재한다면, 현재 인덱스(i)와 보완 숫자의 인덱스를 반환
                return new int[] { numMap[complement], i };
            }

            // 현재 숫자가 Dictionary에 없으면 추가
            // 중복된 키는 허용되지 않으므로 기존 값을 덮어쓰지 않음
            if (!numMap.ContainsKey(nums[i])) {
                numMap[nums[i]] = i;
            }
        }

        // 입력 데이터가 항상 유효하다는 조건이 있지만, 그렇지 않은 경우 예외 발생
        throw new InvalidOperationException("No solution found");
    }
}

 

[시간 복잡도]

반복문 : 배열을 한 번 순회하므로 O(n)

Dictionary 의 검색 및 삽입은 O(1) 이므로

전체 시간 복잡도는 O(n) 이 됩니다.

 

 

[공간 복잡도]

추가로 사용하는 Dictionary 의 크기는 최대 nums.Length 와 같으므로 공간 복잡도는 O(n) 입니다.