solution_python/018 4Sum.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 018 4Sum\n",
    "- 笔记作者：CV七少\n",
    "- 学习时间：2020.6.26\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/4sum/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "\n",
    "给定一个包含` n `个整数的数组` nums `和一个目标值` target`，判断` nums `中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与` target `相等？找出所有满足条件且不重复的四元组。  \n",
    "注意：答案中不可以包含重复的四元组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "- 示例 1:\n",
    "    ```\n",
    "    给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。\n",
    "\n",
    "    满足要求的四元组集合为：\n",
    "    [\n",
    "      [-1,  0, 0, 1],\n",
    "      [-2, -1, 1, 2],\n",
    "      [-2,  0, 0, 2]\n",
    "    ]\n",
    "    ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> 双指针\n",
    "```\n",
    "执行用时：100 ms, 在所有 Python3 提交中击败了86.85%的用户\n",
    "内存消耗：13.6 MB, 在所有 Python3 提交中击败了6.52%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        p = 0 # p, k, i, j\n",
    "        while p < n - 3:  # 文中提到的条件1和条件2，可以直接跳过\n",
    "            if nums[p] + 3 * nums[p + 1] > target: break  \n",
    "            if nums[p] + 3 * nums[-1] < target:           \n",
    "                while p < n - 4 and nums[p] == nums[p + 1]: p += 1\n",
    "                p += 1\n",
    "                continue\n",
    "            k = p + 1\n",
    "            while k < n - 2:   # k 和 p 的判断是一样的\n",
    "                if nums[p] + nums[k] + 2 * nums[k + 1] > target: break\n",
    "                if nums[p] + nums[k] + 2 * nums[-1] < target: \n",
    "                    while k < n - 3 and nums[k] == nums[k + 1]:\n",
    "                        k += 1\n",
    "                    k += 1\n",
    "                    continue\n",
    "                i = k + 1\n",
    "                j = n - 1\n",
    "                new_target = target - nums[p] - nums[k]\n",
    "                while i < j:\n",
    "                    if nums[i] + nums[j] > new_target: j -= 1\n",
    "                    elif nums[i] + nums[j] < new_target: i += 1\n",
    "                    else:\n",
    "                        res.append([nums[p],nums[k],nums[i],nums[j]])\n",
    "                        i += 1\n",
    "                        j -= 1\n",
    "                        while i < j and nums[i] == nums[i - 1]: i += 1 # 避免结果重复\n",
    "                        while i < j and nums[j] == nums[j + 1]: j -= 1 # 避免结果重复\n",
    "                while k < n - 3 and nums[k] == nums[k + 1]: k += 1\n",
    "                k += 1\n",
    "            while p < n - 4 and nums[p] == nums[p + 1]: p += 1\n",
    "            p += 1\n",
    "        return res\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:    nums = [1, 0, -1, 0, -2, 2]  target = 0\n",
    "               output:   [\n",
    "                            [-1,  0, 0, 1],\n",
    "                            [-2, -1, 1, 2],\n",
    "                            [-2,  0, 0, 2]\n",
    "                          ]\n",
    "\"\"\"\n",
    "nums = [1, 0, -1, 0, -2, 2]\n",
    "target = 0\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.fourSum(nums, target)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法二：**</font> 哈希表\n",
    "```\n",
    "执行用时：124 ms, 在所有 Python3 提交中击败了78.68%的用户\n",
    "内存消耗：17.8 MB, 在所有 Python3 提交中击败了6.52%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: [[-1, 0, 0, 1], [-2, 0, 0, 2], [-2, -1, 1, 2]]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        N = len(nums)\n",
    "        if N < 4:\n",
    "            return []\n",
    "        # use set to deduplicate\n",
    "        res = set()\n",
    "        nums.sort()\n",
    "        # sum:[(index1, index2)]\n",
    "        table = {}\n",
    "\n",
    "        for i in range(N - 1):\n",
    "            for j in range(i + 1, N):\n",
    "                s = nums[i] + nums[j]\n",
    "                if target - s in table:\n",
    "                    for tmp in table[target - s]:\n",
    "                        if tmp[1] < i:\n",
    "                            # use tuple since it is hashable\n",
    "                            res.add((nums[tmp[0]], nums[tmp[1]], nums[i], nums[j]))\n",
    "                if s not in table:\n",
    "                    table[s] = []\n",
    "                table[s].append((i, j))\n",
    "        # convert set to list\n",
    "        ans = []\n",
    "        for r in res:\n",
    "            ans.append(list(r))\n",
    "        return ans\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:    nums = [1, 0, -1, 0, -2, 2]  target = 0\n",
    "               output:   [\n",
    "                            [-1,  0, 0, 1],\n",
    "                            [-2, -1, 1, 2],\n",
    "                            [-2,  0, 0, 2]\n",
    "                          ]\n",
    "\"\"\"\n",
    "nums = [1, 0, -1, 0, -2, 2]\n",
    "target = 0\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.fourSum(nums, target)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法三：**</font> 深度优先搜索\n",
    "```\n",
    "执行用时：40 ms, 在所有 Python3 提交中击败了65.51%的用户\n",
    "内存消耗：13.8 MB, 在所有 Python3 提交中击败了5.41%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def letterCombinations(self, digits):\n",
    "        \"\"\"\n",
    "        :type digits: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        return self.nSum(nums, target, 4)\n",
    "\n",
    "    def nSum(self, nums, target, n):\n",
    "        def dfs(pos, cur, n, target):\n",
    "            if n == 2:\n",
    "                j = pos\n",
    "                k = len(nums) - 1\n",
    "                while j < k:\n",
    "                    sum = nums[j] + nums[k]\n",
    "                    if sum < target:\n",
    "                        j += 1\n",
    "                    elif sum > target:\n",
    "                        k -= 1\n",
    "                    else:\n",
    "                        solution = cur[:] + [nums[j], nums[k]]\n",
    "                        ans.append(solution)\n",
    "                        while j < k and nums[j] == nums[j+1]:\n",
    "                            j += 1\n",
    "                        while j < k and nums[k] == nums[k-1]:\n",
    "                            k -= 1\n",
    "                        j += 1\n",
    "                        k -= 1\n",
    "                return\n",
    "            i = pos\n",
    "            while i < len(nums) - n + 1:\n",
    "                # 剪枝的一种情况\n",
    "                if nums[i] * n > target or nums[-1] * n < target:\n",
    "                    break\n",
    "                # 排除重复数字\n",
    "                if i > pos and nums[i] == nums[i-1]:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                cur.append(nums[i])\n",
    "                dfs(i+1, cur, n-1, target-nums[i])  # 回溯\n",
    "                cur.pop()\n",
    "                i += 1\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        dfs(0, [], n, target)\n",
    "        return ans\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:   digits = \"23\"\n",
    "               output:   [\"ad\", \"ae\", \"af\", \"bd\", \"be\", \"bf\", \"cd\", \"ce\", \"cf\"]\n",
    "\"\"\"\n",
    "digits = \"23\"\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.letterCombinations(digits)\n",
    "print('输出为:', result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-gao-su-jie-fa-by-ml-zimingmeng/\n",
    "2. https://leetcode-cn.com/problems/4sum/solution/fei-shuang-zhi-zhen-er-ha-xi-biao-jiang-4shu-zhi-h/\n",
    "3. https://leetcode-cn.com/problems/4sum/solution/shen-du-you-xian-sou-suo-yi-ci-xing-jie-jue-nsum-9/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如果你觉得有用的话：\n",
    "- 请点点 **star** 呦\n",
    "- 关注我的 [CSDN博客](https://mp.csdn.net/console/article)\n",
    "- 关注我的 [哔哩哔哩](https://space.bilibili.com/424394389/channel/detail?cid=132513)\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
}