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.
You can return the answer in any order.
Examples:
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation:
Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 10 9
- -109 <= target <= 10 9
- Only one valid answer exists.
Approach 1 (Brute-force: Two Pointers)
- Loop through all pairs of elements in the array using two nested loops.
- For each pair (i, j), check if
nums[i] + nums[j] === target. - If yes, return the indices
[i, j].
Time Complexity:
Time Complexity = O(n2)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input: nums = [4, 1, 2] target = 3
State Transitions:
Initialize: → n = nums.length = 3 First loop: i = 0 Inner loop: j = 1 → nums[0] + nums[1] = 4 + 1 = 5 ≠ 3 → continue Inner loop: j = 2 → nums[0] + nums[2] = 4 + 2 = 6 ≠ 3 → continue Second loop: i = 1 Inner loop: j = 2 → nums[1] + nums[2] = 1 + 2 = 3 === target → return [1, 2]
Final Output: [1, 2]
Final State: Loop exited early after finding the pair at indices 1 and 2.
Visualisation:
var twoSum = function(nums, target) {
let n = nums.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
let sum = nums[i] + nums[j];
if (sum === target) {
return [i, j];
}
}
}
}
def twoSum(nums, target):
n = len(nums)
for i in range(n - 1):
for j in range(i + 1, n):
sum = nums[i] + nums[j]
if sum == target:
return [i, j]
public class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
int sum = nums[i] + nums[j];
if(sum == target) {
return new int[] {i, j};
}
}
}
return new int[0];
}
}
#include <vector>
using namespace std;
vector twoSum(vector& nums, int target) {
int n = nums.size();
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
int sum = nums[i] + nums[j];
if(sum == target) {
return {i, j};
}
}
}
return {};
}
#include <stdio.h>
void twoSum(int nums[], int n, int target, int result[2]) {
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
int sum = nums[i] + nums[j];
if(sum == target) {
result[0] = i;
result[1] = j;
return;
}
}
}
}
using System;
using System.Collections.Generic;
public class Solution {
public int[] TwoSum(int[] nums, int target) {
int n = nums.Length;
for(int i = 0; i < n - 1; i++) {
for(int j = i + 1; j < n; j++) {
int sum = nums[i] + nums[j];
if(sum == target) {
return new int[] { i, j };
}
}
}
return new int[0];
}
}
Optimal Approach: HashMap
- Store all elements with their indices in a map
(map[nums[i]] = i). - Iterate through the array again to find the complement
(target - nums[i]). - Check if the complement exists in the map and is not the same index.
Returnthe pair of indices [i, map[complement]] as the result.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: nums = [4, 1, 2] target = 3
State Transitions:
Step 1: Initialize → n = nums.length = 3 → map = {}
First Loop (Building the map):
i = 0 → map[4] = 0 → map = { 4: 0 }
i = 1 → map[1] = 1 → map = { 4: 0, 1: 1 }
i = 2 → map[2] = 2 → map = { 4: 0, 1: 1, 2: 2 }
Second Loop (Finding the pair):
i = 0
→ pairToFind = target - nums[0] = 3 - 4 = -1
→ -1 not in map → continue
i = 1
→ pairToFind = 3 - 1 = 2
→ 2 in map AND map[2] !== 1 → True
→ return [1, 2]
Final Output: [1, 2]
Final State: Loop exited early after finding the pair at indices 1 and 2.
var twoSum = function(nums, target) {
let n = nums.length;
let map = {};
for(let i = 0; i < n; i++) {
map[nums[i]] = i;
}
for(let i = 0; i < n; i++) {
let pairToFind = target - nums[i];
if (pairToFind in map && map[pairToFind] !== i) {
return [i, map[pairToFind]];
}
}
};
def twoSum(nums, target):
map = {}
for i in range(len(nums)):
map[nums[i]] = i
for i in range(len(nums)):
pairToFind = target - nums[i]
if pairToFind in map and map[pairToFind] != i:
return [i, map[pairToFind]]
import java.util.HashMap;
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int pairToFind = target - nums[i];
if (map.containsKey(pairToFind) && map.get(pairToFind) != i) {
return new int[] { i, map.get(pairToFind) };
}
}
return new int[0];
}
}
#include <vector>
#include <unordered_map>
using namespace std;
vector twoSum(vector& nums, int target) {
unordered_map map;
for (int i = 0; i < nums.size(); i++) {
map[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i++) {
int pairToFind = target - nums[i];
if (map.count(pairToFind) && map[pairToFind] != i) {
return {i, map[pairToFind]};
}
}
return {};
}
#include <stdio.h>
#include <stdlib.h>
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
for (int i = 0; i < numsSize; i++) {
for (int j = i + 1; j < numsSize; j++) {
if (nums[i] + nums[j] == target) {
int* result = (int*)malloc(2 * sizeof(int));
result[0] = i;
result[1] = j;
*returnSize = 2;
return result;
}
}
}
*returnSize = 0;
return NULL;
}
using System.Collections.Generic;
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary map = new Dictionary();
for (int i = 0; i < nums.Length; i++) {
map[nums[i]] = i;
}
for (int i = 0; i < nums.Length; i++) {
int pairToFind = target - nums[i];
if (map.ContainsKey(pairToFind) && map[pairToFind] != i) {
return new int[] { i, map[pairToFind] };
}
}
return new int[0];
}
} 
Add A Comment
