LintCode - 89 K数之和

浅浅的花香味﹌ 2023-10-12 13:13 1阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[89 · K数之和 - LintCode][89 _ K_ - LintCode]

### 题目描述 ###

给定 n 个不同的正整数，整数 k (k≤n)以及一个目标数字 target。　  
在这 n 个数里面找出 k 个数，使得这 k 个数的和等于目标数字，求问有多少种方案？

### 示例 ###

样例 1：

> 输入：A = \[1,2,3,4\], k = 2, target = 5  
> 输出：2  
> 解释：1 + 4 = 2 + 3 = 5

样例 2：

> 输入：A = \[1,2,3,4,5\], k = 3, target = 6  
> 输出：1  
> 解释：只有这一种方案。 1 + 2 + 3 = 6

### 题目解析 ###

本题的K数之和有一定的局限性，因为本题要求的k元组：

*  是从n个正整数中选择k个数
 *  且最终求出的k元组不需要去重

这使得本题的难度略有下降。

本题可以转化为：01背包问题的装满背包的方案数问题

关于01背包问题的装满背包的方案数问题，解法可以参考：

[LeetCode - 494 目标和\_伏城之外的博客-CSDN博客][LeetCode - 494 _-CSDN]

一般的，01背包问题的装满背包的方案数问题是：

> 有n个物品（n个正整数），物品的重量（整数值），
> 
> 有一个背包，承重为target，
> 
> 问装满背包的方式有多少种？

本题转化的，01背包问题的装满背包的方案数问题是：

> 有n个物品（n个正整数），物品的重量（正整数值），
> 
> 有一个背包，承重为target，
> 
> 现在要在n个物品中必选k个，
> 
> 问装满背包的方案数有多少种？

可以发现，本题的01背包问题，要比一般的01背包问题，多了一维，即必选k个的实现的。

我们定义一个三维数组 dp\[n\]\[k\]\[t\]，代表在0 ~ n 物品中，选择k个，装满承重为 t 的背包的方案总数。

状态转义方程的推导：

*  假设第n个物品不选的话：dp\[n\]\[k\]\[t\] = dp\[n-1\]\[k\]\[t\]
 *  假设第n个物品选的话：dp\[n\]\[k\]\[t\] = dp\[n-1\]\[k\]\[t\] + dp\[n-1\]\[k-1\]\[t - a\[n\]\] （t >= a\[n\]）

这里为什么假设第n个物品选的话，dp\[n\]\[k\]\[t\]的总方案数还要加上dp\[n-1\]\[k\]\[t\]呢？

具体原因情况：[LeetCode - 494 目标和\_伏城之外的博客-CSDN博客][LeetCode - 494 _-CSDN]

状态转义方程的推导其实和“一般的01背包问题的装满背包的方案数问题”的没有区别。

注意点：

*  dp\[n\]\[k\]\[t\] 三维遍历中，对于k维的遍历，需要注意上限k的选择不能超过n维的值，即假设n=4，k=5，即你无法从4个正整数数，选择出五元组。
 *  滚动数组优化时，注意 t 维（背包承重维度）需要三重循环的中间层。

### JS算法源码 ###

三维数组解法：

export class Solution {
      /**
       * @param a: An integer array
       * @param k: A positive integer (k <= length(A))
       * @param target: An integer
       * @return: An integer
       */
      kSum(nums, k, target) {
        // write your code here
        const n = nums.length;
    
        const dp = new Array(n + 1)
          .fill(0)
          .map(() =>
            new Array(k + 1).fill(0).map(() => new Array(target + 1).fill(0))
          );
    
        for (let i = 0; i <= n; i++) dp[i][0][0] = 1;
    
        for (let i = 1; i <= n; i++) {
          const num = nums[i - 1];
          for (let j = 1; j <= Math.min(i, k); j++) {
            for (let t = 1; t <= target; t++) {
              if (t >= num) {
                dp[i][j][t] = dp[i - 1][j][t] + dp[i - 1][j - 1][t - num];
              } else {
                dp[i][j][t] = dp[i - 1][j][t];
              }
            }
          }
        }
    
        return dp[n][k][target];
      }
    }

[提交详情 - LintCode][- LintCode]

滚动数组优化解法：

export class Solution {
      /**
       * @param a: An integer array
       * @param k: A positive integer (k <= length(A))
       * @param target: An integer
       * @return: An integer
       */
      kSum(nums, k, target) {
        // write your code here
        const n = nums.length;
    
        const dp = new Array(k + 1)
          .fill(0)
          .map(() => new Array(target + 1).fill(0));
    
        dp[0][0] = 1;
    
        for (let i = 1; i <= n; i++) {
          const num = nums[i - 1];
          for (let t = target; t >= num; t--) {
            for (let j = 1; j <= Math.min(i, k); j++) {
              dp[j][t] = dp[j][t] + dp[j - 1][t - num];
            }
          }
        }
    
        return dp[k][target];
      }
    }

[提交详情 - LintCode][- LintCode 1]

### Java算法源码 ###

三维数组解法

public class Solution {
        /**
         * @param a: An integer array
         * @param k: A positive integer (k <= length(A))
         * @param target: An integer
         * @return: An integer
         */
        public int kSum(int[] nums, int k, int target) {
            // write your code here
            int n = nums.length;
    
            int[][][] dp = new int[n + 1][k + 1][target + 1];
    
            for (int i = 0; i <= n; i++) {
                dp[i][0][0] = 1;
            }
    
            for (int i = 1; i <= n; i++) {
                int num = nums[i - 1];
                for (int j = 1; j <= Math.min(i, k); j++) {
                    for (int t = 1; t <= target; t++) {
                        if (t >= num) {
                            dp[i][j][t] = dp[i - 1][j][t] + dp[i - 1][j - 1][t - num];
                        } else {
                            dp[i][j][t] = dp[i - 1][j][t];
                        }
                    }
                }
            }
    
            return dp[n][k][target];
        }
    }

[提交详情 - LintCode][- LintCode 2]

滚动数组优化解法

[提交详情 - LintCode][- LintCode 3]

### Python算法源码 ###

三维数组解法

class Solution:
        """
        @param nums: An integer array
        @param k: A positive integer (k <= length(A))
        @param target: An integer
        @return: An integer
        """
        def k_sum(self, nums, k, target):
            # write your code here
            n = len(nums)
    
            dp = [[[0 for _ in range(target+1)] for _ in range(k+1)] for _ in range(n+1)]
    
            for i in range(n+1):
                dp[i][0][0] = 1
    
            for i in range(1, n+1):
                num = nums[i-1]
                for j in range(1, min(i+1, k+1)):
                    for t in range(1, target+1):
                        if t >= num:
                            dp[i][j][t] = dp[i - 1][j][t] + dp[i - 1][j - 1][t - num]
                        else:
                            dp[i][j][t] = dp[i - 1][j][t]
    
            return dp[n][k][target]

[提交详情 - LintCode][- LintCode 4]

滚动数组优化解法

class Solution:
        """
        @param nums: An integer array
        @param k: A positive integer (k <= length(A))
        @param target: An integer
        @return: An integer
        """
        def k_sum(self, nums, k, target):
            # write your code here
            n = len(nums)
    
            dp = [[0 for _ in range(target+1)] for _ in range(k+1)]
    
            dp[0][0] = 1
    
            for i in range(1, n+1):
                num = nums[i-1]
                for t in range(target, num-1, -1):
                    for j in range(1, min(i+1, k+1)):
                        dp[j][t] = dp[j][t] + dp[j - 1][t - num]
    
            return dp[k][target]

[提交详情 - LintCode][- LintCode 5]

[89 _ K_ - LintCode]: https://www.lintcode.com/problem/89/description
[LeetCode - 494 _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/130318724?spm=1001.2014.3001.5501
[- LintCode]: https://www.lintcode.com/submission/31293871/?action_type=1
[- LintCode 1]: https://www.lintcode.com/submission/31294018/?action_type=1
[- LintCode 2]: https://www.lintcode.com/submission/31293883/?action_type=1
[- LintCode 3]: https://www.lintcode.com/submission/31294023/?action_type=1
[- LintCode 4]: https://www.lintcode.com/submission/31293975/?action_type=1
[- LintCode 5]: https://www.lintcode.com/submission/31294031/?action_type=1