## DEV Community Lewis Lloyd

Posted on • Updated on

# 1. Two Sum

## Python

### 🥇 Hash table - O(n)

Method: Take each number and check if its complement has been seen before. If not, add it to the list of known complements along with its index.

• Time complexity: O(n)
• Space complexity: O(n)
``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
"""Take each number and check if its complement has been seen before. If not,
add it to the list of known complements along with its index.

Args:
nums (List[int]): Input array of integers
target (int): Target integer

Returns:
List[int]: Indices of the two integers that sum to target
"""
# Initialise hash map to store known integers
complements = {}
# Iterate through the list
for i in range(len(nums)):
# Check if the current number's complement has been seen before
complement = target - nums[i]
if complement in complements:
return [complements[complement], i]
# Add the current number to the list of known complements
complements[nums[i]] = i
``````

### 🥈 Check pairs - O(n²)

Method: Take each pair of numbers and see if they add up to the target.

• Time complexity: O(n²)
• Space complexity: O(1)
``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
"""Take each pair of numbers and see if they add up to the target.

Args:
nums (List[int]): Input array of integers
target (int): Target integer

Returns:
List[int]: Indices of the two integers that sum to target
"""
# Get length of input array
n = len(nums)
# Iterate over all pairs (i,j)
for i in range(n):
for j in range(i + 1, n):
# Check if this pair equals the target
if nums[i] + nums[j] == target:
return [i, j]
``````

DEV Community

Timeless DEV post...

## Git Concepts I Wish I Knew Years Ago

The most used technology by developers is not Javascript.

It's not Python or HTML.

It hardly even gets mentioned in interviews or listed as a pre-requisite for jobs.

I'm talking about Git and version control of course. 