 # LeetCode #1 Two Sum Solution & Explanation

Content

## LeetCode Problem

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.

This problem is easy to understand.

Find out two interger with different index and add up to the target interger.

## Solution

When I saw this problem, the first easiest way I thought is using the nested loop.

And let’s see how it work.

### C# Solution

Solution1 (use nested loop)

``````public class Solution {
public int[] TwoSum(int[] nums, int target) {

int max = nums.Length;                  //the length of the array

for(int i = 0;i<max;i++)                //find from the first element
{

//the difference of the array element with the target number
int diff = target - nums[i];
for(int j = i+1;j<max;j++)          //can't use the same index,so need to plus 1
{
if(nums[j] == diff)             //when nums[j] equals the diff, return the indices
{
return new int{i,j};
}
}
}
return  new int{0,0};                //useless code, add for complete the return
}
}``````

Solution2 (use Array.FindIndex function)

``````public class Solution {
public int[] TwoSum(int[] nums, int target) {

int max = nums.Length;                  //the length of the array
int index;

for(int i = 0;i<max;i++)                //find from the first element
{

//the difference of the array element with the target number
int diff = target - nums[i];
index = Array.FindIndex(nums,i+1,x=>x == diff);

//if the diff number index have found
if(index != -1)
{
return new int{i,index};
}
}
return  new int{0,0};
}
}``````

Solution3 (use Dictionary to check the key contain)

``````public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
int diff = target - nums[i];
if (dict.ContainsKey(diff))
{
return new int[] {dict[diff], i};
}
if (!dict.ContainsKey(nums[i]))
{
}
}
return new int[]{0,0};
}
}``````

### Java Solution

Solution1

``````class Solution {
public int[] twoSum(int[] nums, int target) {

int max = nums.length;

for(int i = 0;i<max;i++)
{
int diff = target - nums[i];
for(int j=i+1;j<max;j++)
{
if(nums[j] == diff)
{
return new int[]{i,j};
}
}
}
return new int[]{0,0};
}
}``````

Runtime 60ms, not very good, maybe need to try another way.

Solution2 (turn to list and use subList to imitate C# Array.FindIndex function)

❌the concept is rigth, but it will take too long time and cause a Time Limit Exceeded.

you can pass all the testcase, but too slow for this problem.

``````class Solution {
public int[] twoSum(int[] nums, int target) {

int max = nums.length;
int index;
List<Integer> myList = new ArrayList<>();

for(int i = 0;i<max-1;i++)
{
int diff = target - nums[i];

myList = IntStream.of(nums).boxed().collect(Collectors.toList());
myList = myList.subList(i+1,max);
index = myList.indexOf(diff);

if(index != -1)
{
return new int[]{i,index+i+1};
}
}
return new int[]{0,0};
}
}``````

Solution3 Recommend (use hash map to store the value and index)

``````class Solution {
public int[] twoSum(int[] nums, int target) {

HashMap<Integer, Integer>map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++)
{
int diff = target - nums[i];

if (map.containsKey(diff))
{
return new int[] {map.get(diff), i};
}
else
{
map.put(nums[i], i);
}

}
return new int[]{0,0};
}
}``````

⭐Runtime – 3ms

### Python3 Solution

Solution1 (Not recommend)

❌It has a high probability of causing a Time Limit Exceeded

``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
left = nums[i+1:]
for j in range(len(left)):
if (nums[i] + left[j]) == target:
return i, j+i+1``````

Let us try another way !

Solution2 (using hash table for the faster speed)

``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_table={}
for i in range(len(nums)):     #First, create the hash table
hash_table[nums[i]]=i

for i in range(len(nums)):
if target-nums[i] in hash_table:
if hash_table[target-nums[i]] != i:
return [i, hash_table[target-nums[i]]]
return [0,0]``````

### JavaScript Solution

Solution1 (Not recommend)

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for(var i = 0 ; i < nums.length ; i++){
var v = nums[i];

for(var j = i+1 ; j < nums.length ; j++ ){
if(  nums[i] + nums[j]  == target ){
return [i,j];
}
}

}
};``````

Solution2 ( using map to store)

``````/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
var map = {};
for(var i = 0 ; i < nums.length ; i++){
var n = nums[i];

if(map[target-n] >= 0){
return [map[target-n],i]
}
else {
map[n] = i;   //use map to store the value and index position
}
}
};``````

## Conclusion

This problem is the first problem in LeetCode. (Also a Blind 75 problem)

The important point of this problem is to reduce the time complexity. (Time complexity – Wikipedia)

Look at the solution first, nested loop = O(n2) , that’s not a good solution (if the data is very big, than it may cause many unnecessary time cost ).

So, you need to know some data type (hash ,dictionary, etc.), that can help you write your code with different solution.

🧡If my solution helps, that is my honor!

🧡Here to see the next problem ➡ LeetCode #2 Add Two Numbers Solution & Explanation – zyrastory Code & Food Research Center

```"Success is the sum of small efforts - repeated day in and day out."
Robert Collier```

Cover Photo – Image by Ulrike Leone from Pixabay

The problem link : Two Sum – LeetCode

Technology Article

Related Post

1. #### Ashwin

Easy to digest! thanks

• #### zyrastory

Hope it helps🧡