如何在整数数组中找到总和为 K 的元素？
How can I find elements in an integer array that add up to K?
给定一个整数数组和一个数字 k。在数组中找到加起来为 k 的元素组合。最近我遇到一道编程题，题目是给定一个正整数数组 A 和 k。
令 A = {4, 15, 7, 21, 2} 且 k = 13
我的算法应该 return 加起来为 k 的元素的索引列表。在这种情况下：[0,2,4]。每个元素只能使用一次。
我将如何着手解决这个问题？还有时间和 space 的复杂性。
这是这个问题的动态规划解决方案，我在 transaction optimizer 内为崛起币编写了它。
算法思路：创建[k+1]个元素的数组。这个数组中的索引是总和，可以通过一些输入值来达到，而数组中的值 - 输入的数量，用于达到这个总和。值 -1 表示当前元素子集无法达到此总和。
让我们看看你的例子。在您的示例中，k=13，我们最初从 -1 的 14 创建数组 DP：
DP = (-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)
空输出集（sum = 0）可以通过任何方式到达，因此，我们向 DP[0] 存入一些 non-minus_1，例如 - 0。结果，DP[0 ] == 0:
DP = ( 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)
此后，对于数组 A[i] 中的所有输入值，请执行以下操作：
- 向后迭代数组 DP
- 如果 DP[j] >= 0 && DP[j + A[i]] < 0 那么 DP[j + A[i]] = i;
有一个想法：如果在前面的某个步骤中达到了总和 "j"，并且我们有值 A[i]，那么可以通过添加第 i 个元素来达到总和 "j+A[i]"数组 A.
在我们的示例中，添加 A[0]==4 后，我们将得到 DP:
DP = ( 0 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1)
这个零的意思是：A[0] 可以达到和“4”。
尝试添加 A[1] = 15。对于 i=1，DP[19] 和 dp[15] 有两个可能的位置。两者都超出数组范围，所以我们只是不更新 DP 数组。
尝试添加 A[2] = 7。对于 i=2，DP[11] 和 dp[7] 有两个可能的位置。更新后，DP 数组将是：
DP = ( 0 -1 -1 -1 0 -1 -1 2 -1 -1 -1 2 -1 -1)
跳过A[3] == 21，与A[1]相同。
尝试添加 A[4] = 2。DP 数组将是：
DP = ( 0 -1 4 -1 0 -1 4 2 -1 4 -1 2 -1 4)
输入数组A[]耗尽，DP数组准备好解释。我们看到，DP[13] >= 0，因此达到和 13。 DP[13] == 4，所以 A[4] 达到和“13”。记住它。将 DP 数组视为链表，其中值指的是前一个位置。所以，prev = 13-2 = 11。我们看到，A[2] 也包含在总和中。记住“2”。上一个位置：prev = 11-7 = 4。参见 DP[4]。有“0”。也记得 [0]。 Prev = 4-4 = 0。我们到达 DP[0]，停止解释。因此，我们在 A[4,2,0].
中收集了记住的索引
问题已解决。
给定一个整数数组和一个数字 k。在数组中找到加起来为 k 的元素组合。最近我遇到一道编程题，题目是给定一个正整数数组 A 和 k。
令 A = {4, 15, 7, 21, 2} 且 k = 13 我的算法应该 return 加起来为 k 的元素的索引列表。在这种情况下：[0,2,4]。每个元素只能使用一次。
我将如何着手解决这个问题？还有时间和 space 的复杂性。
这是这个问题的动态规划解决方案，我在 transaction optimizer 内为崛起币编写了它。
算法思路：创建[k+1]个元素的数组。这个数组中的索引是总和，可以通过一些输入值来达到，而数组中的值 - 输入的数量，用于达到这个总和。值 -1 表示当前元素子集无法达到此总和。
让我们看看你的例子。在您的示例中，k=13，我们最初从 -1 的 14 创建数组 DP：
DP = (-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)
空输出集（sum = 0）可以通过任何方式到达，因此，我们向 DP[0] 存入一些 non-minus_1，例如 - 0。结果，DP[0 ] == 0:
DP = ( 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)
此后，对于数组 A[i] 中的所有输入值，请执行以下操作：
- 向后迭代数组 DP
- 如果 DP[j] >= 0 && DP[j + A[i]] < 0 那么 DP[j + A[i]] = i;
有一个想法：如果在前面的某个步骤中达到了总和 "j"，并且我们有值 A[i]，那么可以通过添加第 i 个元素来达到总和 "j+A[i]"数组 A.
在我们的示例中，添加 A[0]==4 后，我们将得到 DP:
DP = ( 0 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1)
这个零的意思是：A[0] 可以达到和“4”。
尝试添加 A[1] = 15。对于 i=1，DP[19] 和 dp[15] 有两个可能的位置。两者都超出数组范围，所以我们只是不更新 DP 数组。
尝试添加 A[2] = 7。对于 i=2，DP[11] 和 dp[7] 有两个可能的位置。更新后，DP 数组将是：
DP = ( 0 -1 -1 -1 0 -1 -1 2 -1 -1 -1 2 -1 -1)
跳过A[3] == 21，与A[1]相同。
尝试添加 A[4] = 2。DP 数组将是：
DP = ( 0 -1 4 -1 0 -1 4 2 -1 4 -1 2 -1 4)
输入数组A[]耗尽，DP数组准备好解释。我们看到，DP[13] >= 0，因此达到和 13。 DP[13] == 4，所以 A[4] 达到和“13”。记住它。将 DP 数组视为链表，其中值指的是前一个位置。所以，prev = 13-2 = 11。我们看到，A[2] 也包含在总和中。记住“2”。上一个位置：prev = 11-7 = 4。参见 DP[4]。有“0”。也记得 [0]。 Prev = 4-4 = 0。我们到达 DP[0]，停止解释。因此，我们在 A[4,2,0].
中收集了记住的索引问题已解决。