solution_python/001 Two Sum.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 001 Two Sum\n",
    "- 笔记作者：CV七少\n",
    "- 学习时间：2020.6.3\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/two-sum/  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "给定一个整数数组`nums`和一个目标值`target`，请你在该数组中找出和为目标值的那**两个**整数，并返回他们的数组下标。  \n",
    "\n",
    "你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "`给定 nums = [2, 7, 11, 15], target = 9`  \n",
    "\n",
    "`因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> 暴力枚举法，时间复杂度：$O(n^2)$\n",
    "```\n",
    "执行用时 :6812 ms, 在所有 Python3 提交中击败了5.96%的用户\n",
    "内存消耗 :14.7 MB, 在所有 Python3 提交中击败了12.80%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [0, 1]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"   \n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] + nums[j] == target:\n",
    "                    return[i, j]\n",
    "                \n",
    "\"\"\"\n",
    "For Example:    input:   nums = [2, 7, 11, 15]  target = 9\n",
    "               output:   [0, 1]\n",
    "\"\"\"             \n",
    "nums = [2, 7, 11, 15]\n",
    "target = 9\n",
    "\n",
    "solution = Solution()\n",
    "result = solution.twoSum(nums, target)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法二：**</font> 两边找法，时间复杂度：$O(n)$  \n",
    "\n",
    "Tips: 需要注意的是使用这种方法的前提是列表有序（本题无序），无序可以先[排序](https://github.com/xiaoxuebajie/algorithm)，但是排序之后需要找回原来的index，可以建立一个映射关系，所以如果只是针对此题，不建议使用，但是这种思路很好，对于有序列表且多维度搜索有奇效。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [0, 1]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        j = len(nums) - 1\n",
    "        while i < j:\n",
    "            sum = nums[i] + nums[j]\n",
    "            if sum == target:\n",
    "                return [i ,j]\n",
    "            elif sum < target:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:   nums = [2, 7, 11, 15]  target = 9\n",
    "               output:   [0, 1]\n",
    "\"\"\"             \n",
    "nums = [2, 7, 11, 15]\n",
    "target = 9\n",
    "\n",
    "solution = Solution()\n",
    "result = solution.twoSum(nums, target)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法三：**</font> 哈希法，时间复杂度：$O(n)$\n",
    "```\n",
    "执行用时 :84 ms, 在所有 Python3 提交中击败了48.61%的用户\n",
    "内存消耗 :15.1 MB, 在所有 Python3 提交中击败了5.48%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为： [0, 1]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        dic = {}\n",
    "        for index, num in enumerate(nums):\n",
    "            if target - num in dic:\n",
    "                return [dic[target-num], index]\n",
    "            else:\n",
    "                dic[num] = index\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:   nums = [2, 7, 11, 15]  target = 9\n",
    "               output:   [0, 1]\n",
    "\"\"\"             \n",
    "nums = [2, 7, 11, 15]\n",
    "target = 9\n",
    "\n",
    "solution = Solution()\n",
    "result = solution.twoSum(nums, target)\n",
    "print('输出为：', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 图解:\n",
    "引用的图片展示的是方法四的动态过程，可以帮助分析，很不错\n",
    "<img src='./images/1.gif' style='zoom=10%'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://github.com/MisterBooo/LeetCodeAnimation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如果你觉得有用的话：\n",
    "- 请点点 **star** 呦\n",
    "- 关注我的 [CSDN博客](https://mp.csdn.net/console/article)\n",
    "- 关注公众号：CV伴读社\n",
    "<img src='./images/qrcode.jpg' style='zoom:100%'>"
   ]
  }
 ],
 "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}