个人网站搭建平台,metropro wordpress,深圳网站建设 设计科技有限公司,宝塔 wordpress 规则文章目录一. 题目描述二. 解法① 暴力破解② 静态哈希表1. 为什么用哈希表来做2. 特殊情况#xff1a;两数相同#xff0c;map映射覆盖③ 动态哈希表④ 未解之谜诶嘿#xff0c;经典开头题目 一. 题目描述
数组中同一个元素不能使用两遍#xff1a;
见实例2#xff0c;实…
文章目录一. 题目描述二. 解法① 暴力破解② 静态哈希表1. 为什么用哈希表来做2. 特殊情况两数相同map映射覆盖③ 动态哈希表④ 未解之谜诶嘿经典开头题目 一. 题目描述
数组中同一个元素不能使用两遍
见实例2实际过程可能出现输出为[0,0]的情况就是同一元素使用了两遍要注意判断 二. 解法
① 暴力破解
看到题干首选暴力。 只需要遍历数组对于数组中的每一个元素都和后面的所有元素进行一次匹配即可。
class Solution {public int[] twoSum(int[] nums, int target) {for(int i0;;i){for(int ji1;jnums.length;j){if(nums[i]nums[j]target)return new int[]{i,j};}}}
}时间复杂度为O(n2n^2n2)空间复杂度为O(1)
现在题目解出来了但是要怎么优化呢 看到上述的时空复杂度可以这么想时间复杂度和空间复杂度不太均衡可不可以试一下把时间上的负担分一点到空间上呢
② 静态哈希表
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger, Integer hashtable new HashMapInteger, Integer();// 先构建哈希表for(int i0;inums.length; i)hashtable.put(nums[i],i);// 再遍历数组结合哈希表进行查找for(int i0;inums.length; i){if(hashtable.containsKey(target - nums[i])){// 这边这个判断不能少否则出现同一元素使用两次的情况if(hashtable.get(target - nums[i])!i)return new int[]{hashtable.get(target - nums[i]),i};}}return new int[0];}
}时间复杂度O(n)空间复杂度O(n)
1. 为什么用哈希表来做
暴力法的时间复杂度由来n(遍历数组元素* n(查找能和当前数组组合成target的元素。 而这个查找的O(n)如果是用哈希表来实现则是O(1)。 而由于需要构建出哈希表我们需要付出O(n)的空间复杂度代价。
2. 特殊情况两数相同map映射覆盖
描述使用两个数据值相同下标不同的元素。而我们在建立映射表时使用的键值是数据值因此下标大的元素会覆盖之前的元素变成新的映射导致有些映射会丢失。
理解考虑了好久。。。其实这样子不会出问题。
首先保留的是下标大的元素的映射然后我们在遍历时使用的是数组而且是先遇到下标小的元素。 对这个小的元素进行哈希表查找刚好可以找到下标大的元素。就可以得到正确的结果
③ 动态哈希表
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger, Integer hashtable new HashMapInteger, Integer();for (int i 0; i nums.length; i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
}时间复杂度O(n)空间复杂度O(n)目前了解的最好的方法在②的基础上会比较好理解在②之上的优化
不需要进行相同元素的判断当出现与之前值相同并且可以组成target的值时就直接满足return条件了。 比如实例3先存储30映射到nums[1]的时候不需要覆盖31映射而是满足if判断直接返回[01]。占用的时间空间会更小因为是一边建哈希表一边找answer的所以很大概率在完全建表之前就找到answer。
④ 未解之谜 这一块是无伤大雅但是想弄明白的地方 增强型for循环溢出 这个解决了应该把nums改成nums.length还是用得不够熟悉。
// 正常for循环不会出错
for(int i0;inums.length; i)hashtable.put(nums[i],i);
// 增强型for循环会出现越界错误
for(int i : nums)hashtable.put(nums[i],i);需要额外写return
// ②③如果只有if的return编译器会报错“missing return statement”但是①却不需要
return new int[0];
