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)
1def twoSum(nums, target):
2 for i in range(len(nums)):
3 for j in range(i + 1, len(nums)):
4 if nums[i] + nums[j] == target:
5 return [i, j]
6
7nums = [2, 7, 11, 15]
8target = 9
9result = twoSum(nums, target)
10print(result)The Python solution uses two nested loops to traverse the list. It checks for a pair whose sum equals the target. When such a pair is found, it returns their indices in a list.
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)
1using System;
2using System.Collections.Generic;
3
4class Program {
5 static int[] TwoSum(int[] nums, int target) {
6 Dictionary<int, int> map = new Dictionary<int, int>();
7 for (int i = 0; i < nums.Length; i++) {
8 int complement = target - nums[i];
9 if (map.ContainsKey(complement)) {
10 return new int[] { map[complement], i };
11 }
12 map[nums[i]] = i;
13 }
14 return new int[] {};
15 }
16
17 static void Main() {
18 int[] nums = { 2, 7, 11, 15 };
19 int target = 9;
20 int[] result = TwoSum(nums, target);
21 Console.WriteLine($"[{result[0]}, {result[1]}]");
22 }
23}The C# solution uses a dictionary to track each number and its index. As we iterate through the array, we calculate each number's complement and check if it exists in the dictionary, thereby providing an efficient solution.