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 <stdio.h>
2
3void twoSum(int* nums, int numsSize, int target, int* returnSize) {
4 *returnSize = 2;
5 int result[2];
6 for (int i = 0; i < numsSize; i++) {
7 for (int j = i + 1; j < numsSize; j++) {
8 if (nums[i] + nums[j] == target) {
9 result[0] = i;
10 result[1] = j;
11 printf("[%d, %d]\n", result[0], result[1]);
12 return;
13 }
14 }
15 }
16}
17
18int main() {
19 int nums[] = {2, 7, 11, 15};
20 int numsSize = sizeof(nums) / sizeof(nums[0]);
21 int target = 9;
22 int returnSize;
23 twoSum(nums, numsSize, target, &returnSize);
24 return 0;
25}The C solution uses two nested for loops to iterate through the array. The outer loop selects the first element, and the inner loop checks every subsequent element for a pair whose sum equals the target. If such a pair is found, their indices are printed.
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)
1def twoSum(nums, target):
2 hashmap = {}
3 for i, num in enumerate(nums):
4 complement = target - num
5 if complement in hashmap:
6 return [hashmap[complement], i]
7 hashmap[num] = i
8
9nums = [2, 7, 11, 15]
10target = 9
11result = twoSum(nums, target)
12print(result)The Python solution uses a dictionary to store the numbers and their indices. As we iterate through the list, we determine the complement and check if it's already stored in the dictionary. If yes, it is a solution to the problem.