Two Sum

class Solution {
public:
    vector<int> findTwoSum(vector<int> &numbers, int goal) {
        unordered_map<int, int> num_to_index;
        for (int index = 0; index < numbers.size(); ++index) {
            int needed_part = goal - numbers[index];
            if (num_to_index.find(needed_part) != num_to_index.end()) {
                return {num_to_index[needed_part], index};
            }
            num_to_index[numbers[index]] = index;
        }
        return {};
    }
};

The given solution in C++ addresses the Two Sum problem where the goal is to find two indices in an array such that the numbers at those indices add up to a specific target. The solution efficiently leverages an unordered map to store the indices of the numbers as values, making the lookup operation constant time, O(1).

To implement the solution:

• Define the function findTwoSum, which accepts a vector of integers and the target integer.
• Create an unordered_map to store each element's value and its corresponding index.
• Iterate through the vector of numbers using a for-loop.
• For each element, calculate the difference between the target goal and the current element. This value is referred to as needed_part.
• Check if needed_part exists in the map:
  • If it does, return a vector containing the indices of needed_part and the current element.
• If no complement is found for the current element, add the element and its index to the map.
• If no pair matches the target sum after checking all elements, return an empty vector.

This approach ensures that each element is compared only once, making the function run in linear time, O(n), where n is the number of elements in the vector.

class Solution {
    public int[] findTwoSum(int[] nums, int target) {
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int idx = 0; idx < nums.length; idx++) {
            int difference = target - nums[idx];
            if (indexMap.containsKey(difference)) {
                return new int[] { indexMap.get(difference), idx };
            }
            indexMap.put(nums[idx], idx);
        }
        return new int[] {};
    }
}

The solution implements a method to solve the two-sum problem using Java. The method, findTwoSum, accepts an array of integers nums and a target integer target. The core idea is to use a HashMap (indexMap) to store the elements of the array as keys and their indices as values.

• Iterate through each element of the nums array.
• Calculate the difference needed to reach the target for each element.
• Check if this difference exists in the indexMap:
  • If true, a pair that sums up to the target is found. Return these two indices.
• If the difference is not yet in the map, add the current element and its index to the indexMap.
• If no such pair is found after iterating through the array, return an empty array.

This approach leverages the HashMap to efficiently check for the existence of the required pair component in constant time, resulting in a linear time complexity overall.

int* findTwoSum(int* elements, int length, int sum, int* returnCnt) {
    struct hashMap {
        int num;
        int idx;
        UT_hash_handle hh;
    } *hashMap = NULL, *ele;
    
    for (int index = 0; index < length; index++) {
        int needed = sum - elements[index];
        HASH_FIND_INT(hashMap, &needed, ele);
        if (ele) {
            int* solution = malloc(sizeof(int) * 2);
            solution[0] = ele->idx;
            solution[1] = index;
            *returnCnt = 2;
            HASH_CLEAR(hh, hashMap);  // Clean up the hash map
            return solution;
        }
        ele = malloc(sizeof(struct hashMap));
        ele->num = elements[index];
        ele->idx = index;
        HASH_ADD_INT(hashMap, num, ele);
    }
    *returnCnt = 0;
    HASH_CLEAR(hh, hashMap);  // Clean up the hash map
    return malloc(0);  // Allocate zero bytes for no solution scenario
}

The provided C code implements a solution to the classic "Two Sum" problem, where you need to find two numbers in an array that add up to a specific sum. Review the key features and workings of the code:

• The program utilizes a hash map to store array elements and their indices for quick lookup.
• It iterates through the array, calculates the complement of the current element with respect to the target sum.
• If the complement exists in the hash map (indicating that a pair sums up to the target), the indices of these two elements are returned.
• If not, the current element and its index are added to the hash map for future reference.
• Memory dynamic allocation (malloc) ensures that only the necessary amount of memory is used.
• Proper memory cleanup is handled with HASH_CLEAR to prevent memory leaks.
• The function returns the indices of the two numbers that add up to the target sum if such a pair is found. If no such pair exists, it returns a NULL pointer allocated with zero bytes.

Ensure appropriate memory management when integrating or modifying this code, as improper use of malloc and failure to free memory can lead to memory leaks in larger applications.

var findTwoIndices = function (array, goal) {
    const indicesMap = new Map();
    for (let index = 0; index < array.length; index++) {
        const difference = goal - array[index];
        if (indicesMap.has(difference)) {
            return [indicesMap.get(difference), index];
        }
        indicesMap.set(array[index], index);
    }
    return [];
};

The solution for the "Two Sum" problem is implemented in JavaScript. The function named findTwoIndices involves finding two indices of elements in a given array that add up to a specific target value, goal.

• Initialize a new Map called indicesMap to store each element's value and its index as you iterate through the array.
• Loop through the array using a for loop, with index representing the current position in the array.
• Calculate the difference between the goal and the current element array[index].
• Check if this difference already exists as a key in indicesMap. If it does, return an array containing the mapped index of the difference and the current index.
• If the difference is not found in indicesMap, add the current array element and its index to the map.
• If no such pair is found after iterating through the entire array, return an empty array.

This approach ensures efficient look-ups and insertions, leveraging the properties of a JavaScript Map object to handle the indices and values. The resulting solution is streamlined and performs well with larger datasets.

class Solution:
    def findTwoSum(self, numbers: List[int], goal: int) -> List[int]:
        number_index_map = {}
        for index, number in enumerate(numbers):
            needed = goal - number
            if needed in number_index_map:
                return [index, number_index_map[needed]]
            number_index_map[number] = index
        return []

This Python 3 solution for the "Two Sum" problem efficiently finds two indexes in a list where the values at those indexes sum up to a specified target. The solution utilizes a dictionary (number_index_map) to store and check for the required pair in a single pass through the list:

• Create a dictionary number_index_map to hold the numbers and their respective indices.
• Iterate through the list numbers using enumerate to get both index and number.
• Calculate the needed value that, when added to the current number, equals the goal.
• If needed is already in number_index_map, then the pair making up the goal has been found. Return these indices as a list.
• If not found, add the current number and its index to number_index_map.
• If no such pair is found during the loop, return an empty list.

This method provides an optimal solution with a time complexity of O(n), where n is the number of elements in the input list, because each element is processed once.