置顶 |

LeetCode1995.统计特殊四元组：「哈希表」&「背包DP & 一维」


浏览次数 :  次   
博文字数统计 : 1.6k字   |   阅读所需时长 : 7分
× 文章目录
  1. 1. LeetCode1995.统计特殊四元组：「哈希表」&「背包DP & 一维」
    1. 1.1. 1. 题目描述
    2. 1.2. 2. 方法一：哈希表
    3. 1.3. 3. 方法二：哈希表+两数之和
    4. 1.4. 4. 方法三：动态规划(多维背包)
    5. 1.5. 参考资料
  • LeetCode1995：统计特殊四元组
    • 时间：2021-12-29
    • 力扣难度：Easy
    • 个人难度：Medium
    • 数据结构：一维数组
    • 算法：哈希表、动态规划、多维背包问题

LeetCode1995.统计特殊四元组：「哈希表」&「背包DP & 一维」

1. 题目描述

  • 题目：原题链接

    • 给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同四元组 (a, b, c, d) 的数目
    • 条件：
      • nums[a] + nums[b] + nums[c] == nums[d]
      • a < b < c < d
    • 注意同样值的数字可以多次使用

  • 输入输出规范

    • 输入：数组nums
    • 输出：四元组个数

  • 输入输出示例

    • 输入：nums = [1,1,1,3,5]
    • 输出：4

2. 方法一：哈希表

  • 思路：哈希表

    • 暴力解法：暴力枚举，四重循环，复杂度过高
    • 使用哈希表存d的值
    • 三重遍历，匹配 a+b+c = d
    • 注意：将元素添加到哈希表的操作可以和查询、匹配哈希表的操作放在同一个循环下面，无需分开进行

  • 复杂度分析：n是数组长度

    • 时间复杂度：$O(n^3)$，三重循环，嵌套遍历a，b，c
    • 空间复杂度：$O(min(n,C))$，其中C是数组中的元素范围，即最大值，在本题中 C = 100在，哈希表中会存放C个数据

  • 题解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public int countQuadruplets(int[] nums) {
        int res = 0;
        if(nums == null || nums.length == 0) return res;
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        for (int c = n - 2; c >= 2; c--) {
            map.put(nums[c+1], map.getOrDefault(nums[c+1], 0)+1);

            for (int b = c-1; b >= 1; b--) {
                for (int a = b - 1; a >= 0 ; a--) {
                    res += map.getOrDefault(nums[a]+nums[b]+nums[c], 0);
                }
            }
        }
        return res;
    }

3. 方法二：哈希表+两数之和

  • 思路：哈希表

    • 使用哈希表存 d-c 的值
    • 双重遍历，匹配 a+b = d-c
    • 在枚举前两个下标 a, b 时，可以先逆序枚举 b
    • 在 b 减小的过程中，c 的取值范围是逐渐增大的：即从 b+1减小到 b 时，c 的取值范围中多了 b+1 这一项，而其余的项不变
    • 因此我们只需要将所有满足 c=b+1 且 d>c 的 c, d 对应的 d-c 加入哈希表即可

  • 复杂度分析：n是数组长度

    • 时间复杂度：$O(n^2)$，双重循环，嵌套遍历a，b，在遍历a的同时遍历d，两者之间无嵌套的关系
    • 空间复杂度：$O(min(n,C)^2)$，其中C是数组中的元素范围，哈希表中会存放$C*(C-1)$个数据，对应d和c的组合个数

  • 题解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public int countQuadruplets(int[] nums) {
        int res = 0;
        if (nums == null || nums.length == 0) return res;
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int b = n - 3; b >= 1; b--) {
            for (int d = b + 2; d < n; d++) {
                map.put(nums[d] - nums[b + 1], map.getOrDefault(nums[d] - nums[b + 1], 0) + 1);
            }

            for (int a = 0; a < b; a++) {
                res += map.getOrDefault(nums[a] + nums[b], 0);
            }
        }
        return res;
    }

  • 图解

    LC1995哈希表+两数之和解法示意图

4. 方法三：动态规划(多维背包)

  • 思路：动态规划(多维背包)

    • 本题的元素都是正数，且 $1<=nums[i]<=100$ ，符合背包问题的数值特点
    • 利用等式关系 $nums[a] + nums[b] + nums[c] = nums[d]$，具有明确的「数值」和「个数」关系，可将问题抽象为组合优化问题求方案数
    • 限制组合个数的维度有两个，均为「恰好」限制，转换为「二维费用背包问题求方案数」问题
    • 状态定义：dp[i][j][k]表示前 $i$ 个物品，凑成数值恰好为 $j$ ，同时使用物品的个数恰好为 $k$ 个的方案的个数，可见：物品就是数组的元素，且三个元素凑成第四个元素的值，即 $k = 3$，$j = nums[d]$，$1 <= i <= length(nums)$
    • 最终结果：方案数为 $∑_{i=3}^{n-1}=dp[i][nums[i]][3]$，表示前 $i$ 元素中的三个元素等于第 $i$ 个元素的方案个数
    • 边界条件：$dp[0][0][0] = 1$，表示使用0个物品(元素)凑成数值为0的方案个数是一个
    • 状态转移方程：根据 $nums[i - 1]$ 是否参与组合进行分情况讨论
      • 不参与讨论：$dp[i][j][k]=dp[i-1][j][k]$
      • 参与讨论：$dp[i][j][k]=dp[i-1][j - nums[i-1]][k-1]$
    • 整合：$dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j - nums[i-1]][k-1]$
    • 维度优化：因为 $dp[i][j][k]$ 仅依赖于 $dp[i-1][j][k]$ 和 $dp[i-1][j - nums[i-1]][k-1]$，所以可以优化空间复杂度

  • 复杂度分析：n是数组长度

    • 时间复杂度：$O(kn)$，$kn$ 表示创建的 $dp[i][j][k]$ 数组的容量
    • 空间复杂度：$O(k*n)$

  • 题解：三维背包

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public int countQuadruplets(int[] nums) {
        int res = 0;
        if (nums == null || nums.length == 0) return res;
        int n = nums.length;
        int[][][] dp = new int[n + 1][101][4];
        dp[0][0][0] = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                for (int k = 0; k < dp[0][0].length; k++) {
                    dp[i][j][k] += dp[i - 1][j][k];
                    if (j - nums[i - 1] >= 0 && k - 1 >= 0) {
                        dp[i][j][k] += dp[i - 1][j - nums[i - 1]][k - 1];
                    }
                }
            }
        }
        for (int i = 3; i < n; i++) {
            res += dp[i][nums[i]][3];
        }
        return res;
    }

  • 进阶优化：二维背包

    • 维护二维数组 $dp[k][j]$：$k$ 表示选择的元素个数，$k = 0,1,2,3$，$j$ 表示元素的数值和

    • 二维数组 $dp[k][j]$ 表示 $k$ 个元素凑成值 $j$ 的方案个数

    • 遍历物品(元素)数组，统计选三个元素的各值中该数的个数就是答案的一部分

    • 代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      public int countQuadruplets(int[] nums) {
          int[][] dp = new int[4][101];
          dp[0][0] = 1;
          int ans = 0;
          for(int num : nums){
              ans += dp[3][num];
              for(int j=dp.length-1;j>0;j--)
                  for(int i=num;i<dp[0].length;i++)
                      dp[j][i] += dp[j-1][i-num];
          }
          return ans;
      }

  • 下一步学习计划：背包问题

参考资料

本文作者： Chthollists
发布时间： 2021-12-29 23:58:35
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode1995.统计特殊四元组：「哈希表」&「背包DP & 一维」
本文链接： https://chthollists.github.io/post/cf89cc9c.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
知识共享许可协议
支持

感谢您的支持

支付宝
微信
置顶

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

<font color="purple" face="Microsoft YaHei" size= 5><b>待到雄图卷毕 &nbsp;&nbsp;隐居山水里<br>坐看炊烟旖旎 &nbsp;&nbsp;浅池戏双鲤<br> </b></font>