[neetcode] Two Integer Sum

난이도

• Easy

문제 설명

정수 배열 nums와 정수 target이 주어집니다. nums[i] + nums[j] == target이고 i != j인 인덱스 i와 j를 반환하세요.\n 모든 입력에는 이 조건을 만족하는 정확히 하나의 인덱스 쌍이 존재한다고 가정할 수 있습니다.\n 더 작은 인덱스가 먼저 오는 답을 반환하세요.

입력 형식

• 정수 배열

출력 형식

• 정수 배열

예제 입력 및 출력

**예제 1:**
입력: nums = [3, 4, 5, 6], target = 7
출력: [0, 1]
설명: nums[0] + nums[1] == 7이므로 [0, 1]을 반환합니다.

**예제 2:**
입력: nums = [4, 5, 6], target = 10
출력: [0, 2]

**예제 3:**
입력: nums = [5, 5], target = 10
출력: [0, 1]

접근 방법

• 해시맵 사용: 각 숫자와 그 인덱스를 저장하기 위해 해시맵을 사용합니다.
• 두 번째 반복: 배열을 다시 순회하면서 각 숫자의 보수를 계산하고, 해시맵에 해당 보수가 존재하는지 확인합니다.
• 인덱스 확인: 보수가 해시맵에 존재하고, 그 인덱스가 현재 인덱스와 다르면 결과를 반환합니다

  시간 및 공간 복잡도

• 시간 복잡도: O(n) - 모든 배열을 한번 순회해야함
• 공간 복잡도 : O(1) - 해시맵을 사용하여 최대 n개의 요소를 저장해야 함

코드 구현

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numsMap = new HashMap<>();
        for(int i = 0; i < nums.length;i++){
            numsMap.put( nums[i],i);
        }

        
        for(int i = 0; i < nums.length;i++){
            int minusValue = target - nums[i];
            if(numsMap.containsKey(minusValue) && numsMap.get(minusValue) != i){
                return new int[]{i, numsMap.get(minusValue)};
            }
        }
        return new int[0];

    }
}