🔧 🚀 Solving the Two Sum Problem: Multiple Approaches Using Java/Python

🕛 Zeit seit Veröffentlichung: 47 Tage, 8 Stunden 16 Minuten
📆 Veröffentlicht am: 22.08.2024 um 15:24 Uhr
Nachrichtenbereich: 🔧 Programmierung
🔗 Quelle: dev.to

The "Two Sum" problem is a popular coding challenge that tests your ability to find pairs in an array that sum up to a specific target. Let’s dive into various methods to solve this problem efficiently.

Problem Statement 🎯

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.

Example

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

Output: [0, 1] (because nums[0] + nums[1] == 9)

1. Brute Force Approach ⚔️

Python:

def two_sum_bruteforce(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Java:

public int[] twoSumBruteforce(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[] {}; // If no solution is found
}

Explanation:

Iterate over each pair of indices and check if their sum equals the target.

2. Hash Map Approach 📚

Python:

def two_sum_hash_map(nums, target):
    num_to_index = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], i]
        num_to_index[num] = i
    return []

Java:

import java.util.HashMap;

public int[] twoSumHashMap(int[] nums, int target) {
    HashMap<Integer, Integer> numToIndex = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (numToIndex.containsKey(complement)) {
            return new int[] { numToIndex.get(complement), i };
        }
        numToIndex.put(nums[i], i);
    }
    return new int[] {}; // If no solution is found
}

Explanation:

Use a hash map to store the index of each number.
For each element, check if its complement (target - current number) exists in the hash map.

3. Two-Pointer Approach 🏃‍♂️

Python:

def two_sum_two_pointer(nums, target):
    nums_with_index = list(enumerate(nums))
    nums_with_index.sort(key=lambda x: x[1])

    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums_with_index[left][1] + nums_with_index[right][1]
        if current_sum == target:
            return [nums_with_index[left][0], nums_with_index[right][0]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

Java:

import java.util.Arrays;
import java.util.Comparator;

public int[] twoSumTwoPointer(int[] nums, int target) {
    int[][] numsWithIndex = new int[nums.length][2];
    for (int i = 0; i < nums.length; i++) {
        numsWithIndex[i][0] = i;
        numsWithIndex[i][1] = nums[i];
    }
    Arrays.sort(numsWithIndex, Comparator.comparingInt(a -> a[1]));

    int left = 0, right = nums.length - 1;
    while (left < right) {
        int currentSum = numsWithIndex[left][1] + numsWithIndex[right][1];
        if (currentSum == target) {
            return new int[] { numsWithIndex[left][0], numsWithIndex[right][0] };
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[] {}; // If no solution is found
}

Explanation:

First, sort the array while keeping track of the original indices.
Use two pointers to find the pair that sums up to the target.

4. Optimized Space Approach 🔍

Python:

def two_sum_optimized(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        diff = target - num
        if diff in seen:
            return [seen[diff], i]
        seen[num] = i
    return []

Java:

import java.util.HashMap;

public int[] twoSumOptimized(int[] nums, int target) {
    HashMap<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int diff = target - nums[i];
        if (seen.containsKey(diff)) {
            return new int[] { seen.get(diff), i };
        }
        seen.put(nums[i], i);
    }
    return new int[] {}; // If no solution is found
}

Explanation:

Iterate through the array while maintaining a hash map of the numbers seen so far.
Check if the complement of the current number exists in the hash map.

Conclusion 🌟

These methods offer various ways to solve the Two Sum problem, each with its advantages and trade-offs. Whether you prefer the straightforward brute force method or the efficient hash map approach, understanding these techniques will enhance your problem-solving skills.

Feel free to share your thoughts or additional methods in the comments!