Algorithm Puzzles ~~everyday~~ ~~every week~~ sometimes: Two Sum

## Puzzle

Puzzle from leetcode:

Given an array of integers, return **indices** of the two numbers such that they add up to a specific target.

You may assume that each input would have **exactly** one solution, and you may not use the same element twice.

Example:

1 | Given nums = [2, 7, 11, 15], target = 9, |

The template code provided by leetcode:

1 | class Solution { |

## Solving

The first came out solution from my head is for every elements for-loop traverse once to find the result:

1 | class Solution { |

It’s really ez! But time complexity will be **O(n^2)** since there are 2 for-loops inside. There must be a better way, I can’t submit with this solution!

So what kind of search method is better? Maybe hash table?

1 | class Solution { |

Bravo! Time complexity is **O(n)** now!(but we used more space)

results:

What? Only better than 88.56%? OK it still can get improvements by replacing for-each with for-loop(But why I choose for-each at the first time…)

1 | class Solution { |

result:

Cool, better than 99.79% now!