[LeetCode] 1. Two Sum (java)

https://leetcode.com/problems/two-sum/description/?source=submission-ac

 

문제 파악

더해서 target값을 가지는 두 요소값의 인덱스를 return하기

• 주어진 input 값을 오직 하나의 솔루션만 가진다.
• 같은 요소를 솔루션으로 가질 수 없다.

Constraints:

• 2 <= nums.length <= 10^4

 

문제 풀이

📌 완전 탐색

• 반복문
• 백트래킹 (재귀)
• 정렬 & 투포인터
• 해시맵

반복문

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 new int[]{-1, -1};
    }
}

 

📊 실행 결과

• Worst Case Time Complexity: 10^8

 

 

재귀

class Solution {
    public int[] twoSum(int[] nums, int target) {
        return backtracking(nums, target, new ArrayList<Integer>(), 0);
    }
    
    private int[] backtracking(int[] nums, int target, List<Integer> list, int startIdx) {
        if (list.size() == 2) {
            if (nums[list.get(0)] + nums[list.get(1)] == target) {
                return new int[]{list.get(0), list.get(1)};
            }
            return null;
        }

        for (int i = startIdx; i < nums.length; i++) {
            list.add(i);
            int[] result = backtracking(nums, target, list, i + 1);
            if (result != null) {  // 정답 발견 시
                return result;
            }
            list.remove(list.size() - 1);
        }

        return null;
    }
}

 

📊 실행 결과

• Worst Case Time Complexity: 10^8 (반복문을 사용해 구현한 것과 동일한 로직이기 때문에, 시간복잡도도 동일)

 

 

Sort & Two Pointer

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Number[] numbers = new Number[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numbers[i] = new Number(nums[i], i);
        }

        Arrays.sort(numbers, (n1, n2) -> n1.number - n2.number);

        int front = 0;
        int rear = nums.length - 1;
        while (front < rear) {
            int sum = numbers[front].number + numbers[rear].number;
            if (sum < target) 
                front++;
            else if (sum > target) 
                rear--;
            else 
                return new int[]{numbers[front].index, numbers[rear].index};
            
        }
        return new int[]{-1, -1};
    }

    class Number {
        int number;
        int index;

        Number(int number, int index) {
            this.number = number;
            this.index = index;
        }
    }
}

 

📊 실행 결과

• 최악의 경우 시간 복잡도는 O(nlogn)이다.

 

 

Hash Table 

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

        for (int i = 0; i < nums.length; i++) {
            if (hashtable.containsKey(nums[i])) {
                result[0] = i;
                result[1] = hashtable.get(nums[i]);
            }
            else {
                hashtable.put(target - nums[i], i);
            }
        }

        return result;
    }
}

 

📊 실행 결과

• 최악의 경우 시간 복잡도는 O(n)이다.

 

 

Note

• Arrays.sort() 메서드
  • 시간 복잡도: O(nlogn)
  • 기본 정렬: 오름차순
  • 객체 배열을 정렬할 때는 Comparator<T>를 사용해야 한다.
  • 사용 예시: Arrays.sort(arr, (o1, o2) -> o1 - o2)