力扣01 求两数之和
题目：
给定一个整数数组，返回两个数字的索引，使它们加起来为一个特定的目标。
您可以假设每个输入只有一个解决方案，并且您可能不会两次使用同一个元素。
示例：
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]
注：题目大意就是在给定的一个数组中找到两个数组元素之和为给定的target并且返回这两个数组元素在数组中的下标。
解法一：暴力求解
解题思路：
依次固定数组的第一个元素，并开始遍历数组（从固定元素的下一个元素开始）看其他元素与固定元素加起来是否等于target若等于则返回这两个数组的下标若不等于则重复此操作。
代码：
/**
* 暴力解决：每次固定一个数再遍历剩余数组中的元素看这两个数之和是否等于target
* 如果等于就返回这两个数在数组中所对应的下标值
*/
public class TowSum01 {
/**
* 定义一个方法返回类型为一个数组，参数为指定的一个数组以及目标值
* 返回的数组元素为对应两个目标数在原来数组中的下标值
* @param nums
* @param target
* @return
*/
public int[] towSum ( int[] nums, int target){
//1.定义一个长度为2的数组用以存储目标数在原来数组中的下标值
int[] result = new int[2];
//2.第一层循环是固定原来数组的元素因为每一个都要固定一次
for (int i = 0; i < nums.length; i++) {
//2.1第二层循环是寻找剩下元素是否有元素与固定的元素加起来值为target
for (int j = i + 1; j < nums.length; j++) {
//2.2将固定元素与剩下的元素加起来看值是否等于target
int sum = nums[i] + nums[j];
if (sum == target) {
//2.3如果sum等于target则将这两个元素的下标放在result数组中并返回result
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
}
解法二：哈希表求解
解题思路：
使用哈希表求解，将原本数组中的元素作为哈希表中的key将数组元素对应的数组下标作为哈希表中的value，并按照此规则将数组放进哈希表中。遍历此哈希表用target-key的值作为参照并在哈希表中查找是否有符合此值的key，若存在符合此值的key则返回此key的value。
代码：
import java.util.Hashtable;
/**
* 使用哈希表法：将原本数组中的元素作为哈希表中的key将原本数组中元素的下标作为哈希表中的value
* 遍历一次原来的数组将按照以上规则放进哈希表中
* 使用target-key看差值在哈希表中是否存在若存在则返回value
*/
public class TowSum02 {
//1.定义一个方法，返回值类型为长度为2的数组，参数为一个数组以及int类型的target
public int[] towSum(int[] nums,int target){
//2.定义一个长度为2的数组用来存储返回的两个value
int[] result = new int[2];
//3.定义一个哈希表用来存储元本数组的元素以及对应元素的下标值
Hashtable<Integer, Integer> map = new Hashtable<>();
//4.遍历原本的数组将元素作为key将下标作为value存储在map中
for (int i = 0; i < nums.length; i++) {
map.put(nums[i],i);
}
//5.遍历数组元素并用target与数组元素做差看其差值是否在map中
for (int j = 0; j < nums.length; j++) {
//5.1 target与数组元素做差
int diff = target - nums[j];
//5.2 看差值是否在map中且不能是同一个元素
if(map.containsKey(diff) && map.get(diff) != j){
//6.将数组的下标值以及map中找到对应key的value（也就是另一个下标值）放进result中
result[0] = j;
result[1] = map.get(diff);
return result;
}
}
return result;
}
}
总结： 解法一的时间复杂度为O(N²)，解法二的时间复杂度为O(N)。