04. 哈希表的使用.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 哈希表\n",
    "\n",
    "特点：查找速度是O(1)  \n",
    "用于：空间换时间\n",
    "\n",
    "常常用于缓存，然后快速查找，提升性能\n",
    "\n",
    "<img src=\"./hashmap-two-number-sum.png\" style=\"margin-left:0px; \"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "问题描述：无序数组中找出和为N的两个数  \n",
    "\n",
    "例如，nums = [1, 4, 3, 2, 6, 5]中找出和为target = 6的序列  \n",
    "\n",
    "答案：[(1, 5), (4, 2)]。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find(num_list, sum_value):\n",
    "    \"\"\"\n",
    "    @param num_list：数字列表\n",
    "    @param sum_value：数字之和\n",
    "    \"\"\"\n",
    "    # 第一遍历，O(N)，建立哈希表\n",
    "    hash_dict = {}\n",
    "    for val in num_list:\n",
    "        if val not in hash_dict:\n",
    "            hash_dict[val] = 0\n",
    "        # value是这个值的出现次数\n",
    "        hash_dict[val] += 1\n",
    "    print(hash_dict)\n",
    "    \n",
    "    # 第二次遍历，O(N)\n",
    "    # 遇到每个元素val，判断sum_value-val在不在哈希表中\n",
    "    for val in num_list:\n",
    "        if hash_dict[val] == 0:\n",
    "            continue\n",
    "        # 使用次数减一\n",
    "        hash_dict[val] -= 1\n",
    "        # 如果减去的数字也在表中，则说明匹配成功\n",
    "        if hash_dict.get(sum_value-val, 0) > 0:\n",
    "            print(val, sum_value-val) \n",
    "            hash_dict[sum_value-val] -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 1, 4: 2, 3: 2, 2: 1, 6: 1, 5: 1}\n",
      "1 5\n",
      "4 2\n",
      "3 3\n"
     ]
    }
   ],
   "source": [
    "num_list = [1, 4, 3, 2, 3, 4, 6, 5]\n",
    "find(num_list, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}