[Leetcode] 1. Two Sum

모르겠는데요

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

example
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

---

접근

• 합산 결과가 target과 일치하게 되는 인덱스를 탐색하자
• 만들고 보니 브루트 포스

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

• O(n^2)
• 효율이 구립니다
• 다른 접근을 찾아봅니다

---

레거시 개선

• 유효한 숫자 쌍 탐색에 실패한 경우 해시 테이블에 현재 요소를 추가합니다

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

        // Build the hash table
        for (int i = 0; i < n; i++) {
            numMap.put(nums[i], i);
        }

        // Find the complement
        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[]{i, numMap.get(complement)};
            }
            if (numMap.get(complement) != i) {
                return new int[]{i, numMap.get(complement)};
            }
        }
        return new int[]{}; 
    }
}

• 아직 정리가 끝나지 않았습니다