LeetCode爬坡——第一题：Two Sum

question description：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.

Analysis：About this question, our primary thinking is to use the way of Vionent search, however, I'm sure that leetcode would never allow us using Vilnent search, because it cause too much time（time complexity is Theta(n^2)). So we need save time at the expense of space complexity.

Solution 1：Refer to the idea of binary search. Firstly, we sort the input array well using the container Vector's function Sort. Then, searching the target at the same time of the sorted array's beginning and end. Finally, output the target's indices.The code is as follows:

the runtime is:

Solution 2：the another way is using the HashMap to build the link between value and indices. As we all know, the HashMap's time complexity is Theta(n). Firstly, we iterate through the array to build the HashMap. Then, we iterate through the array again to find the target and its indices. Finally , output the indices.

the runtime is:

Solution 3：the third way is to use iterator, essentially, the iterator is equal to double loop.but the iterator's execution efficiency is higher, so the runtime is less. The code is as follows:

the runtime is:

Abviously, despite the use of iterator, double loop still cost too much time.