Solving Array Problems: Two Sum
Algorithms and Data Structures From Zero to Hero
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.
Understanding with examples
Example 1:
Input: nums = [1,2,3,4,5], target = 8
Output: [2,4]
Explanation: Because nums[2] + nums[4] == 8, we return [2, 4].Analysis — BigO
Solution 1:
My first solution will be to iterate through the array starting at index 0 and then create a nested loop to iterate through the rest of the array elements.
The value a represents the value of the upper loop and the value b the index of the elements to the right of the array that will be iterated in the inner loop, until the indexes of the two numbers add up to the target.
If a at index 0 plus one of the elements on the right hand side of the array is not the sum of the target, the pointer changes to the next one until aand b add up to the target.
As this is a nested loop, this operation will take O(nxn) which is actually O(n^2).
Solution 2:
I can do it a better.
The second solution will be to create an object. The object will have the value, and the index.
I’ll have to create an obj variable and iterate through the array. On each iteration it will add the item and the related index.
Next, I’ll create another (non-nested) loop, iterate through the array and create a variable augend the number to which an addend is added (mathematical and computer science term for the number on the left in an addition, the number on the right is the addend).
Finally, If the objhas the augend, we return the output.
These separates iterations will take O(n).
Solution 3:
Similar to the second solution but more simple using the map function.
Create a new Map() map and an augend variable, then iterate through the array, get the augend and check if is in the map if isn’t add the value and index to the map until found it.
Code
Solution 1:
Solution 2:
Solution 3:
Summary
This is an easy problem, if there is something you don’t understand don’t be afraid to leave a comment.
This article is part of the series Algorithms and Data Structures From Zero to Hero.
👋 Let’s be friends! Follow me on Twitter and connect with me on LinkedIn. Don’t forget to follow me here on Medium as well.
