Two Sum – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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.
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] <= 109
-109 <= target <= 109
- Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2)
time complexity?
C++ Two Sum LeetCode Solution
vector<int> twoSum(vector<int> &numbers, int target)
{
//Key is the number and value is its index in the vector.
unordered_map<int, int> hash;
vector<int> result;
for (int i = 0; i < numbers.size(); i++) {
int numberToFind = target - numbers[i];
//if numberToFind is found in map, return them
if (hash.find(numberToFind) != hash.end()) {
//+1 because indices are NOT zero based
result.push_back(hash[numberToFind] + 1);
result.push_back(i + 1);
return result;
}
//number was not found. Put it in the map.
hash[numbers[i]] = i;
}
return result;
}
Java Two Sum LeetCode Solution
Hi, this is my accepted JAVA solution. It only go through the list once. It’s shorter and easier to understand. Hope this can help someone. Please tell me if you know how to make this better :)
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[1] = i;
result[0] = map.get(target - numbers[i]);
return result;
}
map.put(numbers[i], i);
}
return result;
}
Python 3 Two Sum LeetCode Solution
The key to the problem is that there is ALWAYS only 1 pair of numbers that satisfy the condition of adding together to be the target value.
We can assume that for all the numbers in the list (x1, x2, … xn) that there exists a pair such that xa + xb = target
To solve this with a single pass of the list we can change the equation above to xa = target – xb and since we know the target as long as we maintain a record of all previous values in the list we can compare the current value (xa) to it’s ONLY pair, if it exists, in record of all previous values (xb)
To keep a record of the previous values and their indices I have used a dictionary. Commonly known as a map in other languages. This allows me to record each previous number in the dictionary alongside the indice as a key value pair (target-number, indice).
class Solution(object):
def twoSum(self, nums, target):
buffer_dictionary = {}
for i in rangenums.__len()):
if nums[i] in buffer_dictionary:
return [buffer_dictionary[nums[i]], i] #if a number shows up in the dictionary already that means the
#necesarry pair has been iterated on previously
else: # else is entirely optional
buffer_dictionary[target - nums[i]] = i
# we insert the required number to pair with should it exist later in the list of numbers
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below