 Coder's Cat

## LeetCode: two sum

2019-10-16

LeetCode sum two: explanations and solutions with Cpp/Java/Python/Ruby

## Explanation

### Naive solutions

First, we come out with the simplest solution, iterate with array element, check whether there are two value’s sum is target, if true, we get a result, so pseudo code is:

Time complexity: $O(N^2)$ Space complexity: $O(1)$

### Optimization with hashmap

Time general idea is use space to optimize time complexity. We can use a hashmap to optimize the second loop from O(N) to O(1).

So we build a hashmap, the key is the element of array, and value is the index of the element. This hashmap can be constructed before hand, but a better way is to construct in the same loop of checking.

Time complexity: $O(N)$ Space complexity: $O(N)$

## Java

Java version is same logic with Cpp version:

## Python

Why we don’t need a hashmap in Python version, please note the second if test. It’s a pragmatic style for Python check whether a element is in array:

Note we use nums[i+1:] in checking, that means we use part of nums index begin with i+1. According to the document, the time complexity of ‘in’ operator is O(N) for list, so this implementation’s time complexity is: $O(N^2)$

## Ruby

Ruby’s version is short, the logic is same with a Hashmap.

Preparing for an interview? Checkout this!

Join my Email List for more insights, It's Free!😋