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.

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

My solution:

 public int[] twoSum(int[] nums, int target) {
for(int i = 0; i < nums.length; i++){
for(int j = 0; j < nums.length; j++){
if(nums[i] + nums[j] == target && i!=j){
return new int [] {i, j};
            }
        }
    }
return null;
}

Runtime：56ms
Your runtime beats 9.43% of java submissions.

显然时间复杂度为O(n^2)，耗时太长，不太合理。

Better Solutions:

以下为其他人提交的时间复杂度为O(n)的算法。

C++

vector<int> twoSum(vector<int> &numbers, int target)
{
//Key is the number and value is its index in the vector.
unordered_map<int, int> hash;
vector<int> result;
for (int i = 0; i < numbers.size(); i++) {
int numberToFind = target - numbers[i];

//if numberToFind is found in map, return them
if (hash.find(numberToFind) != hash.end()) {
//+1 because indices are NOT zero based
            result.push_back(hash[numberToFind] + 1);
            result.push_back(i + 1);            
return result;
        }

//number was not found. Put it in the map.
        hash[numbers[i]] = i;
    }
return result;
}

Java

public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
            result[1] = i + 1;
            result[0] = map.get(target - numbers[i]);
return result;
        }
map.put(numbers[i], i + 1);
    }
return result;
}

Maybe The Shorest Solution

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(map.containsKey(target - nums[i])) 
return new int[] {map.get(target - nums[i]) + 1, i + 1};
else map.put(nums[i], i);
        }
return null;
    }

为什么要用Hashmap？

Hashmap根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，为了将时间复杂度降到O(n)，我们使用了Hashmap。

methods of Hashmap

HashMap()
构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)
构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap
HashMap(int initialCapacity, float loadFactor)
构造一个带指定初始容量和加载因子的空 HashMap
void clear()
从此映射中移除所有映射关系。
boolean containsKey(Object key)
如果此映射包含对于指定的键的映射关系，则返回 true。
boolean containsValue(Object value)
如果此映射将一个或多个键映射到指定值，则返回 true。
V put(K key, V value)
在此映射中关联指定值与指定键。-

在HashMap中通过get()来获取value，通过put()来插入value，ContainsKey()则用来检验对象是否已经存在。可以看出，和ArrayList的操作相比，HashMap除了通过key索引其内容之外，别的方面差异并不大。

使用HashMap后，运行速度相比于原来的275ms确实有明显提升

Runtime: 8ms
Your runtime beats 56.48% of java submissions.

秒客网

【LeetCode刷题记录】1.Two Sum解法与Hashmap的应用