LintCode

admin管理员组

文章数量:1794759

LintCode

LintCode -- k-sum（k数和）

原题链接：/

给定n个不同的正整数，整数k（k < = n）以及一个目标数字。　　　　

在这n个数里面找出K个数，使得这K个数的和等于目标数字，求问有多少种方案？

您在真实的面试中是否遇到过这个题？   Yes 样例

给出[1,2,3,4]，k=2， target=5，[1,4] and [2,3]是2个符合要求的方案

分析：

利用二维数组，像纸币面额问题一样，递归关系：dp[ y ][ z ] += dp[ y-1 ][ z-A[x] ] ，dp[ y ][ z ]代表 y 个数之和为 z 的方案个数。

****  时间复杂度  O（n*k*target）， 空间复杂度 O（k*target）****

代码（C++、Java、Python）：

class Solution {
public:/*** @param A: an integer array.* @param k: a positive integer (k <= length(A))* @param target: a integer* @return an integer*/int kSum(vector<int> A, int k, int target) {// wirte your code here  T(n, k, target) = O(n*k*target). area(n, k, target) = O(k*target)int n = A.size();int dp[k+1][target+1];memset(dp, 0, sizeof(dp));dp[0][0] = 1;for (int x = 0; x < n; x++)for (int y = k; y >= 1; y--)for (int z = target; z >= A[x]; z--)dp[y][z] += dp[y-1][z-A[x]];return dp[k][target];}
};

public class Solution {/*** @param A: an integer array.* @param k: a positive integer (k <= length(A))* @param target: a integer* @return an integer*/public int kSum(int A[], int k, int target) {// write your code here  T(n, k, target) = O(n*k*target). area(n, k, target) = O(k*target)int n = A.length;int [][] dp = new int [k+1][target+1];dp[0][0] = 1;for (int x = 0; x < n; x++)for (int y = k; y >= 1; y--)for (int z = target; z >= A[x]; z--)dp[y][z] += dp[y-1][z-A[x]];return dp[k][target];}
}

class Solution:"""@param A: An integer array.@param k: a positive integer (k <= length(A))@param target: integer@return an integer"""def kSum(self, A, k, target):# write your code here  T(n, k, target) = O(n*k*target). area(n, k, target) = O(k*target)n = len(A)dp = [[0 for z in range(target+1)] for y in range(k+1)]dp[0][0] = 1for x in range(n):for y in list(reversed(range(1, k+1))):for z in list(reversed(range(A[x], target+1))):dp[y][z] += dp[y-1][z-A[x]]return dp[k][target]

本文标签： LintCode