https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150

1. Two Sum

⭐ 문제

정수 배열 nums와 정수 target이 주어졌을때 두 숫자의 합이 target이 되는 인덱스들을 반환하세요.

정확한 하나의 해결책이 있다고 가정합니다. 동일한 요소를 두번쓸 수 없습니다.

시간복잡도 O(n^2) 미만의 알고리즘으로 해결해보세요

🤔 접근 방향

HashTable을 사용하여 더욱 빠르게 조회하고 효율적인 업데이트를 가능하게 하였습니다.

✍️ 의사 코드

1. 계산에 사용될 맵을 선언
2. 배열을 순회하면서 각 요소의 보수를 계산
   2.1 보수가 맵에 존재한다면 보수와 현재값의 인덱스를 리턴
   2.2 존재하지 않는다면 현재 요소와 해당 요소의 인덱스를 해시맵에 저장

✅ 나의 풀이

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> indexMap = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            if (indexMap.containsKey(complement)) {
                return new int[] {indexMap.get(complement), i};
            }
            
            indexMap.put(nums[i], i);
        }
        
        return null;
    }
}

🖥️ 결과

Runtime 0ms