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[2]{i,j};
}
}
}
return new int[2]{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[2]{i,index};
}
}
return new int[2]{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]))
{
dict.Add(nums[i], 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+1Let 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 CollierCover Photo – Image by Ulrike Leone from Pixabay
The problem link : Two Sum – LeetCode
Technology Article
- Understanding Hive ransomware – Preventing becoming the next victim
- How to Effectively Manage Personnel Permissions using Binary-Base Logic Control
- Zambian Central Bank refused to pay ransom to hackers but sent pornographic picture !
Related Post
Easy to digest! thanks
Hope it helps🧡
constantly i used to read smaller articles or reviews which as
well clear their motive, and that is also happening with this piece of writing which I
am reading here.