第二周 笔记

Simona0769 · Simona0769 · commit 1f87bdeee28b · 2020-06-17T22:59:27.000+08:00
diff --git a/Week02/NOTE.md b/Week02/NOTE.md
@@ -1 +1,11 @@
-学习笔记
+# 哈希表、映射、集合的实现与特性
+## Hash table
+* 定义
+  * 哈希表也叫散列表，是根据关键码值（key value）而直接进行访问的数据结构。  
+  * 通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（Hash Function)，存放记录的数组叫哈希表（或散列表）
+* 哈希碰撞（Hash Collisions）
+  * 对于不同的要存储的数据，经过哈希函数之后得到一个相同的值，这就是哈希碰撞
+  * 解决方法：拉链式解决冲突法
+* 工程实践
+  * 缓存（LRU Cache）
+  * 键值对存储（Redis）
diff --git a/Week02/programming/two-sum.js b/Week02/programming/two-sum.js
@@ -0,0 +1,55 @@
+/**
+ * 暴力法
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number[]}
+ */
+var twoSum = function(nums, target) {
+    for (var i = 0; i < nums.length -1 ; i ++) {
+        for (var j = i + 1; j < nums.length; j ++) {
+            if (nums[i] + nums[j] === target) {
+                return [i, j]
+            } 
+        }
+    }
+};
+
+/**
+ * 两遍哈希
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number[]}
+ */
+var twoSum = function(nums, target) {
+    var hashmap = {};
+    for(var i = 0; i < nums.length; i ++) {
+        if (hashmap[nums[i]] === void 0) {
+            hashmap[nums[i]] = i;
+        }
+    }
+    for (var j = 0; j < nums.length; j ++) {
+        var _num = target - nums[j];
+        if (hashmap[_num] !== void 0 && hashmap[_num] !== j) {
+            return [j, hashmap[_num]]
+        }
+    }
+};
+
+/**
+ * 一遍哈希
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number[]}
+ */
+var twoSum = function(nums, target) {
+    let _map = new Map();
+    for(var i = 0; i < nums.length; i ++) {
+        if (!_map.has(nums[i])) {
+            _map.set(nums[i], i);
+        }
+        var _num = target - nums[i];
+        if (_map.has(_num) && _map.get(_num) !== i) {
+            return [_map.get(_num), i]
+        }
+    }
+};
