小小程序员的我准备没事刷刷leetcode的题，顺便把当时的想法记录~
英文原题
Two Sum
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].
中文翻译
两数之和
给定一个整数数组和一个目标值，找出数组中和为目标值的 两个 数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
（数组 哈希表）（难度：简单）
第一次编写总结 ： 这道题考验数组的处理 第一次191ms 性能略差 待优化
第一次思路 ： 第一次就想到遍历，想到到类似排序一样，第一次答的时候没太读懂题意，以为是一个数组中所有等于目标（target）的组合，所以就写的麻烦了一点，还写了一个String数组转Int数组，其实这道题，只输出一组就可以了
时间复杂度 ：双重for循环 n*n = n^2; 来回转换类型肯定浪费时间，后面转换的时候又一次 N级操作 不过总体来说 算法复杂度 O(n^2)
public static int[] twoSum(int[] nums, int target) {
String number = new String();
for(int i = 0; i <nums.length; i++) {
for(int j = i+1;j < nums.length; j++) {
if (nums[i]+ nums[j] == target){
number += i + ",";
number += j + ",";
}
}
}
String[] munber = number.split(",");
int in[] = new int[munber.length];
// 对String数组进行遍历循环，并转换成int类型的数组
for (int i = 0; i < munber.length; i++) {
in[i] = Integer.parseInt(munber[i]);
}
return in;
}
Runtime: 191 ms, faster than 1.00% of Java online submissions for Two Sum.
第二次编写总结 ： 明白题后很重要 把第一次代码进行简化，总体思路还是第一次的 ,总体runtime时间提升 性能提升百分一百三以上
思路 ： 跟第一次一样 只不过明确返回数组大小和循环结束时间break
时间复杂度 ： 依然O(n^2)
public static int[] twoSum(int[] nums, int target) {
int[] number = new int[2];
for(int i = 0; i <nums.length; i++) {
for(int j = i+1;j < nums.length; j++) {
if (nums[i]+ nums[j] == target){
number[0]=i;
number[1]=j;
break;
}
}
}
return number;
}
Runtime: 55 ms, faster than 11.33% of Java online submissions for Two Sum.
第三次编写总结 ： 思考去掉没用的变量创建 增加全局思考 借鉴思想 总体时间提升一倍左右 相当于百分之百
思路 ：可以不用创建新变量 可以不用break停止程序 可以直接返回 增加异常抛出
时间复杂度 ：依然O(n^2)
空间复杂度 ： O(1)
public static int[] twoSum2(int[] nums, int target) {
for(int i = 0; i <nums.length; i++) {
for(int j = i+1;j < nums.length; j++) {
if (nums[j] == target - nums[i]){
return new int []{i,j};
}
}
}
throw new IllegalArgumentException("no two sum solution");
}
Runtime: 24 ms, faster than 36.77% of Java online submissions for Two Sum.
第四次编写总结 ：这道题 主要考点是数组和哈希表 我一直没太理解怎么用到了哈希表，不过通过我的不懈努力（臭不要脸的借鉴），终于懂了
思路 : 我们的目地是为了让时间复杂度从O(n^2) 加速到 O(n) -> O(logn) 乃至 O(1) ,我们找一个数和另一个数等于目标，相当于我们有一个码要找他的互补的码，我们如何从一个码找到一个他的补码呢，如果存在补码，我们需要查找它的索引。保持数组中每个元素到索引的映射的最好方法是什么？哈希表。 而JAVA中什么跟HASH有关系呢 最常用的是hashmap，hashmap在不发生hash碰撞的时候 时间复杂度是O(1) 发生后 它是一个链表的形式 它的复杂度也只是O(n)
时间复杂度：map读的地方是O(1)，但总体还是O(n)
PS :百度百科（我以后也会去看看维基百科的，英语还有待提高） 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
Map<Integer,Integer> mp = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
mp.put(nums[i],i);
}
for (int i = 0; i < nums.length; i++) {
int number = target - nums[i];
if(mp.containsKey(number) && mp.get(number) != i)
return new int[]{i,mp.get(number)};
}
throw new IllegalArgumentException("no two sum solution");
Runtime: 4 ms, faster than 96.28% of Java online submissions for Two Sum.
第五次编写总结 ： 其实相当于第四次 借鉴的时候也借鉴了它的优化版 总体提升不大
思路 ： 从两次for循环中解脱出来，用一个for循环实现 当我们迭代元素并将其插入到表中时，我们还会回头检查当前元素的补码是否已经存在于表中。如果它存在，我们已经找到它并立即返回。
时间复杂度 ： 最大的复杂度还是O(n)
public static int[] twoSum4(int[] nums,int target){
Map<Integer,Integer> mp = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int number = target - nums[i];
if(mp.containsKey(number))
return new int[]{mp.get(number),i};
mp.put(nums[i],i);
}
throw new IllegalArgumentException("no two sum solution");
}
Runtime: 3 ms, faster than 99.85% of Java online submissions for Two Sum.
总结 ： 从简单的数组操作在到哈希表的应用，从性能上看，就可以看出代码优雅的一面，基础学习题也能看出代码的思考。
------WHY 2018.11.21
网友评论