This approach uses a simple brute force algorithm, which consists of checking each pair of numbers to see if they add up to the target. Although this is straightforward, it is not the most efficient method. We loop through each number in the array using two nested loops, effectively trying all combinations of two numbers.
Time Complexity: O(n^2)
Space Complexity: O(1)
1#include <iostream>
2#include <vector>
3
4std::vector<int> twoSum(std::vector<int>& nums, int target) {
5 for (int i = 0; i < nums.size(); ++i) {
6 for (int j = i + 1; j < nums.size(); ++j) {
7 if (nums[i] + nums[j] == target) {
8 return {i, j};
9 }
10 }
11 }
12 return {};
13}
14
15int main() {
16 std::vector<int> nums = {2, 7, 11, 15};
17 int target = 9;
18 std::vector<int> result = twoSum(nums, target);
19 std::cout << "[" << result[0] << ", " << result[1] << "]" << std::endl;
20 return 0;
21}The C++ solution follows a similar approach to C. It uses a vector and iterates over all possible pairs of elements using two nested loops. Once a pair with a sum matching the target is found, the indices are returned.
This efficient approach utilizes a hash map to store the difference between the target and the current element (called 'complement') as the key and the element's index as the value. As we iterate through the array, we check if the current element is a key in the hash map, which indicates that its complement was seen earlier, thus allowing us to retrieve the correct indices quickly.
Time Complexity: O(n)
Space Complexity: O(n)
1function twoSum(nums, target) {
2 const hashmap = {};
3 for (let i = 0; i < nums.length; i++) {
4 let complement = target - nums[i];
5 if (hashmap[complement] !== undefined) {
6 return [hashmap[complement], i];
7 }
8 hashmap[nums[i]] = i;
9 }
10 return [];
11}
12
13let nums = [2, 7, 11, 15];
14let target = 9;
15let result = twoSum(nums, target);
16console.log(result);The JavaScript implementation uses an object to store number indices, providing constant-time complexity for look-up operations. This enables the algorithm to quickly assess whether the complement exists in the map, ensuring the solution is found efficiently.