[array] two sum

✅ Problem

https://leetcode.com/problems/two-sum/description/

 

✅ Approach & Solution

방식1) 브루트 포스로 계산

• 배열 순회하여 모든 조합 확인

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

 

방식2) 첫 번째 수를 뺀 결과 키 조회

• (target - nums[i])에 해당하는 값이 배열에 존재하는지 확인 (Map 사용)

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);
        }

        // target에서 첫 번째 수를 뺀 결과를 키로 조회하고 현재 인덱스가 아닌 경우 정답으로 리턴
        for (int i = 0; i < nums.length; i++) {
            if (numsMap.containsKey(target - nums[i]) && i != numsMap.get(target - nums[i])) {
                return new int[]{i, numsMap.get(target - nums[i])};
            }
        }
        // 조건에서 항상 정답이 존재하므로 널이 리턴되는 경우는 없음
        return null;
    }
}

 

방식3) 조회 구조 개선

• 하나의 for문으로 합치기

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> numsMap = new HashMap<>();

		// 하나의 for문으로 Map 조회 및 원소 삽입
        for (int i = 0; i < nums.length; i++) {
            if (numsMap.containsKey(target - nums[i])) {
                return new int[]{numsMap.get(target - nums[i]), i};
            }
            numsMap.put(nums[i], i);
        }
        
        return null;
    }
}