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].
Tags: Array, Hash Table
翻译题意：简单来说，就是给定一个数组及一个目标数值，求数组中两元素相加为该目标数值对应的两个下标索引。且要求index1小于index2，答案结果稳定。
---------------------------------------------------------------------------------------------------------------------------- 思路：
一、遍历：最粗暴的方法，时间复杂度为O(n^2)。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int index1,index2;
int[] index=new int[]{0,1};
for(int i = 0; i< nums.length; i++)
{
for(int j = i+1; j< nums.length; j++)
{
if(target==(nums[i]+nums[j]))
{
index[0] = i+1;
index[1] = j+1;
return index;
}
}
}
return index;
}
}
二、HashSet：利用HashSet元素不能重复的原理，新建一个HashSet，然后可先检查target-nums[i]能否加入该HashSet，若能，则说明前面的数据没有与第i个符合的组合。在把该target-nums[i]删除，重新添加nums[i]（避免有两个元素相等返回错误判断）。当添加不成功，则说明存在符合的组合，记录此时的i，并从i以前的数组寻找他的另一半。有点繁琐，但时间复杂度为O(n)，空间复杂度为O(n)。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int index1,index2;
int[] index=new int[]{0,1};
Set nset = new HashSet();
for(int i = 0; i< nums.length; i++)
{
if(nset.add(target-nums[i])) //检查是否有nums[i]配对的元素存在，无则添加成功
{
nset.remove(target-nums[i]); //添加该元素只是为了判断是否存在，本来不应该添加的这里又删掉
nset.add(nums[i]);
}else
{
index[1] = i+1;
for(int j = 0; j< i; j++)
{
if(target==(nums[i]+nums[j]))
{
index[0] = j+1;
return index;
}
}
return index;
}
}
return index;
}
}
三、HashMap：用HashMap来做，道理相同，不过跟二还是有点区别。1、HashMap要需要为每个元素创建key和value两个内存空间，辅助空间翻倍。本例子就是用value来放index；2、由于用value来放index，找到一个后，另外一个就马上可以得到其index。二跟三，一个省点空间、一个省点点时间，都差别不大。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] index=new int[]{0,1};
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
for(int i = 0; i<nums.length; i++)
{
if(hm.containsKey(target - nums[i]))
{
index[1] = i+1;
index[0] = hm.get(target-nums[i])+1;
return index;
}else
{
hm.put(nums[i],i);
}
}
return index;
}
}
----------------------------------------------------------------------------------------------------------------------------
