Java에서 Two Sum 문제

Source: Dev.to

Two‑Sum 문제 – Java에서의 다양한 접근법

Two‑Sum 문제는 개발자 채용 면접에서 가장 흔히 나오는 질문 중 하나입니다.
정수 배열과 목표 합(target sum)이 주어지면, 배열에서 두 숫자를 찾아 그 합이 목표와 일치하도록 해야 합니다.

아래는 Java로 구현한 네 가지 고전적인 해결책이며, 가장 단순하지만 가장 느린 방법부터 가장 효율적인 방법 순으로 정렬했습니다.

1️⃣ Brute‑Force (O(n²) 시간, O(1) 공간)

각 요소 x를 순회하면서, x에 대해 배열 나머지 부분을 스캔해 x + y == target이 되는 보완값 y를 찾습니다.

public static int[] getTargetSumIndices(int[] arr, int target) {
    for (int i = 0; i  num) {
            high = mid - 1;
        } else if (arr[mid]  seen = new HashSet<>();

    for (int x : arr) {
        int complement = target - x;
        if (seen.contains(complement)) {
            return new int[]{complement, x}; // found the pair
        }
        seen.add(x);
    }
    return new int[]{-1, -1}; // not found
}

Complexity:

• Time – O(n) (single pass, constant‑time look‑ups).
• Space – O(n) for the hash set.

Summary Table

Choose the implementation that best fits your constraints:

• If you can afford extra space and need the fastest runtime → use the hash‑set method.
• If you must keep space O(1) and the array can be reordered → the two‑pointer technique is ideal.
• For educational purposes or tiny inputs, the brute‑force solution works fine.

Constant‑Time Operations ( O(1) ) for Insertion and Lookup

The code for this approach is as follows:

public static int[] getTargetSumPair(int[] arr, int target) {
    HashSet seen = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        int complement = target - arr[i];
        if (!seen.contains(complement)) {
            seen.add(arr[i]);
        } else {
            return new int[] { arr[i], complement };
        }
    }
    return new int[] { -1, -1 };
}

Complexity Analysis

• Time complexity: O(n) – we iterate through the array once.
  Lookup and insertion operations on a HashSet are O(1) on average.

• Space complexity: O(n) – we store each visited element in the hash set.

Hope you liked reading this blog about the Two Sum problem and the various approaches you can follow to achieve the right result. This is my first algorithm‑related blog on dev.to. Writing blogs has been a really engaging way of learning for me, clarifying my doubts, and sharing my understandings with the community. I aim to clear concepts in a fun way using visual tools like GIFs.

Following this post, I’ll be bringing more such content for the developer community to read and flourish!