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

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)$
C++

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.

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