LeetCode Solution: 1. Two Sum

Your First LeetCode Journey: Conquering 'Two Sum' (Problem 1) with Ease!

Hey fellow developers! 👋 Kushalx here, and today we're diving into the absolute cornerstone of algorithmic problem-solving: LeetCode's very first problem, Two Sum. If you're just starting your LeetCode adventure, this is the perfect place to begin. It's a fantastic problem that introduces powerful concepts you'll use again and again.

Let's break it down, understand the "why" behind the solution, and get you ready to crush future challenges!

1. Problem Explanation

Imagine you have a list of numbers, and a specific "target" number. Your mission, should you choose to accept it, is to find two numbers within that list that add up to your target. Once you find them, you need to return their positions (indices) in the original list.

Here's the official breakdown:

You are given:

An array of integers nums.
An integer target.

You need to:

Return the indices of the two numbers such that they add up to target.

Important Rules:

You can assume that each input would have exactly one solution. No need to worry about multiple pairs or no solution existing!
You may not use the same element twice. If nums[0] is part of the sum, you can't use nums[0] again as the second number.
You can return the answer in any order (e.g., [0, 1] or [1, 0] is fine).

Let's look at a few examples to make it crystal clear:

Example 1:
nums = [2, 7, 11, 15], target = 9

Here, nums[0] (which is 2) + nums[1] (which is 7) equals 9.
So, the output should be [0, 1].

Example 2:
nums = [3, 2, 4], target = 6

nums[1] (which is 2) + nums[2] (which is 4) equals 6.
Output: [1, 2].

Example 3:
nums = [3, 3], target = 6

nums[0] (which is 3) + nums[1] (which is 3) equals 6.
Output: [0, 1]. Notice we use two different elements, even if they have the same value.

Constraints to keep in mind:

The list nums will have at least 2 numbers and at most 10,000 numbers.
Numbers in nums and the target can be quite large or small (between -10^9 and 10^9).

2. Intuition

When faced with a problem like this, a common first thought is often the most straightforward one: "Let's check every possible pair!"

The Brute-Force Idea (and why it's not ideal)

If we wanted to check every single pair, we could do something like this:

Take the first number (nums[0]).
Add it to every other number (nums[1], nums[2], ...).
If any sum equals target, we're done!
If not, take the second number (nums[1]) and add it to every number after it (nums[2], nums[3], ...).
Continue this process until you find a pair.

This approach works! It would definitely find the answer.
However, consider a list with 10,000 numbers.

For the first number, you might check up to 9,999 other numbers.
For the second, up to 9,998.
And so on...

This quickly adds up to a lot of operations. In computer science terms, this is an O(n^2) solution (pronounced "O of n squared"), where n is the number of elements. For n = 10,000, n^2 is 100,000,000 (100 million)! While computers are fast, this can become too slow for larger inputs. The "Follow-up" explicitly asks for something less than O(n^2).

The Smarter Idea: What are we really looking for?

Let's rethink. If we have a currentNumber and we know our target, what's the other number we need to find?
It's simply target - currentNumber. We can call this the complement.

So, for each currentNumber in our list, we need to quickly answer the question: "Has its complement appeared before in the list, and if so, what was its index?"

If we can answer that question very, very fast, we've got a winner!

3. Approach

This is where a magical data structure comes into play: the Hash Map (or Dictionary in Python, HashMap in Java, etc.).

Hash maps allow you to store key-value pairs and, crucially, look up a value by its key in average O(1) time (constant time!). This is incredibly fast, like flipping open a dictionary directly to the word you want.

Here's the refined strategy using a hash map:

Initialize an empty Hash Map: This map will store numbers we've seen so far as keys and their indices as values. (e.g., {number: index}).
Iterate through the nums array: We'll go through each number one by one, keeping track of its index.
For each currentNumber at index i: a. Calculate the complement: complement = target - currentNumber. b. Check if the complement is already in our Hash Map: * If numMap.containsKey(complement) is true: * Eureka! We've found our pair! The complement was seen before, and its index is numMap.get(complement). The currentNumber is at index i. * Return [numMap.get(complement), i]. * If the complement is not in the Hash Map: * This currentNumber isn't the second part of a pair we've seen yet. So, we add the currentNumber itself to our map along with its index, in case it becomes the first part of a pair for a number we see later. * numMap.put(currentNumber, i).

Since the problem guarantees exactly one solution, we know we'll find a pair and return early from the loop. We don't need to worry about the loop finishing without a return.

4. Code

Let's put that approach into action with some Java code.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // Create a HashMap to store numbers and their indices.
        // Key: The number itself
        // Value: The index of that number in the 'nums' array
        Map<Integer, Integer> numMap = new HashMap<>();

        // Iterate through the array 'nums' using an index 'i'
        for (int i = 0; i < nums.length; i++) {
            int currentNum = nums[i]; // Get the current number

            // Calculate the 'complement' needed to reach the target
            // If currentNum + complement = target, then complement = target - currentNum
            int complement = target - currentNum;

            // Check if the 'complement' already exists as a key in our map.
            // If it does, it means we've seen this 'complement' before,
            // and its index is stored as the value associated with the 'complement' key.
            if (numMap.containsKey(complement)) {
                // We found our pair!
                // The index of the complement is numMap.get(complement)
                // The index of the current number is 'i'
                return new int[] { numMap.get(complement), i };
            }

            // If the complement is NOT found in the map, it means the currentNum
            // hasn't found its partner yet. So, we add currentNum to the map
            // along with its index. This way, if a future number's complement
            // is this currentNum, we'll find it.
            numMap.put(currentNum, i);
        }

        // According to the problem constraints, there will always be exactly one solution.
        // Therefore, this line should theoretically never be reached.
        // It's good practice to have a default return, or throw an exception
        // if the problem didn't guarantee a solution.
        return new int[0]; 
    }
}

5. Time & Space Complexity Analysis

Understanding how efficient your code is, is a crucial skill in competitive programming and software engineering.

Time Complexity: O(n)

We iterate through the nums array exactly once.
Inside the loop, operations like numMap.containsKey(), numMap.get(), and numMap.put() take average O(1) (constant) time. In the worst-case (rare for typical hash map implementations), these operations can degrade to O(n), but for practical purposes and competitive programming, we consider them O(1) on average.
Since we perform a constant number of O(1) operations for each of the n elements, the total time complexity is O(n). This is a significant improvement over the O(n^2) brute-force approach!

Space Complexity: O(n)

In the worst-case scenario, we might iterate through almost the entire nums array before finding the pair (e.g., the last two numbers form the target).
In such a case, the numMap would store up to n-1 elements.
Therefore, the space required by the hash map grows linearly with the input size n.
Thus, the space complexity is O(n).

6. Key Takeaways

Hash Maps are your best friend for fast lookups! Whenever you need to quickly check if an element exists or retrieve associated data, think hash map (or dictionary). They convert O(n) or O(n^2) search problems into average O(1).
The "Complement" Strategy: Many problems involving sums or differences can be simplified by thinking about what other number you need to reach a target. complement = target - currentNumber is a powerful pattern.
Trade-offs between Time and Space: We achieved better time complexity (O(n)) by using extra space (O(n)) for the hash map. This is a very common trade-off in algorithms. Sometimes, you'll optimize for space, sometimes for time, depending on the constraints.
Don't start with the most complex solution. Start with the brute-force idea, understand its limitations, and then think about how data structures can help optimize it.

7. Submission Details

Author Account: Kushalx
Publishing Time: 2026-05-24 16:01:11
Problem: 1. Two Sum

This problem is a fantastic stepping stone. Master it, and you've got a solid foundation for many more LeetCode challenges! Keep coding, keep learning, and happy problem-solving! ✨

推荐订阅源

DEV Community