如何在一个整数数组中找到相加为K的元素？ [英] How can I find elements in an integer array that add up to K?

问题描述

给出一个整数数组和一个数字k。在数组中找到总计为k的元素的组合。最近我遇到一个编码问题，给我一个正整数A和k的数组。

Given an array of integers and a number k. Find a combination of elements in the array that add up to k. Recently I got a coding question where I was given an array of positive integers A and k.

让A = {4，15，7，21，2}并且k = 13
并且我的算法应该返回索引的列表总计为k的元素。在这种情况下：[0,2,4]。每个元素只能使用一次。

Let A = {4, 15, 7, 21, 2} and k = 13 and my algorithm was supposed to return a list of indexes of the elements that add up to k. In this case: [0,2,4]. Each element can only be used once.

我将如何解决这个问题？时间和空间的复杂性也将是什么。

How would I go about approaching this problem? Also what would be the time and space complexity.

推荐答案

这是针对此问题的动态编程解决方案，我在交易优化程序。

This is dynamic programming solution for this problem, and I coded it for Emercoin, within transaction optimizer.

算法的思路：您创建[k + 1]个元素的数组。此数组中的索引是总和，可以由某个输入值达到，而具有数组的值-输入数，用于达到该总和。值-1表示，当前元素的子集无法达到该总和。

Idea of algorithm: You create array of [k+1] element. Index in this array is sum, which can be reached by some input value, and value withing array - number of input, used for reach this sum. Value -1 shows, this sum cannot be reached by current subset of elements.

让我们看一下您的示例。在您的示例中，k = 13，我们首先从-1的14中创建数组DP：

Lets see your example. In your example, k=13, and we initially create array DP from 14 of -1:

DP =（-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1）

DP = (-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)

空输出集（sum = 0）可以通过任何方式获得，并且由于它，我们将一些非负数存入DP [0]，例如-0。结果，DP [0] == 0：

empty output set (sum = 0) can be reached in any way, and because of it, we deposit into DP[0] some non-minus_1, for example - 0. as result, DP[0] == 0:

DP =（0- 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1））

DP = ( 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1)

此后，对于数组中的所有输入值A [i]，请执行以下操作：

Thereafter, for all input values from your array A[i], do following:

• 向后迭代数组DP


• 如果DP [j ]> = 0&& DP [j + A [i]]< 0，然后DP [j + A [i]] = i;

有一个主意：如果某项中的总和 j达到上一步，我们得到了值A [i]，则通过从数组A中添加第i个元素，可以得出总和 j + A [i]。

There is idea: if sum "j" was reached in some previous step, and we have value A[i], then sum "j+A[i]" can be reached, by adding i-th element from the array A.

在我们的示例中，添加A [0] == 4后，我们将获得DP：

In our example, after adding your A[0]==4, we will have DP:

DP =（0 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1）

DP = ( 0 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1)

此零表示：A [0]可以达到总和 4。

This zero is meaning: sum "4" can be reached by A[0].

尝试添加A [1] =15。i= 1有两个可能的位置，DP [19]和dp [15]。两者都超出数组范围，所以我们不更新DP数组。

Trying to add A[1] = 15. There is two possible location for i=1, DP[19] and dp[15]. Both out of array bound, so we just don't update DP array.

尝试添加A [2] =7。i= 2有两个可能的位置，DP [11]和dp [7]。更新后，DP数组将为：

Trying to add A[2] = 7. There is two possible location for i=2, DP[11] and dp[7]. After update, DP array will be:

DP =（0 -1 -1 -1 0 -1 -1 -1 2 -1 -1 -1 2 -1 -1 ）

DP = ( 0 -1 -1 -1 0 -1 -1 2 -1 -1 -1 2 -1 -1)

跳过A [3] == 21，与A [1]相同。

Skip A[3] == 21, as same as A[1].

尝试加A [4] =2。DP数组为：

Trying to add A[4] = 2. DP-array would be:

DP =（0 -1 4 -1 0 -1 4 2 -1 4 -1 2- 1 4）

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。上一个位置：上一个= 11-7 =4。请参见DP [4]。有 0。还要记住[0]。上一页= 4-4 =0。我们到达DP [0]，停止解释。因此，我们在A [4,2,0]中收集了记住的索引。

Input array A[] exhaust, DP array is ready for interpretation. We see, DP[13] >= 0, so sum 13 is reached. DP[13] == 4, so sum "13" is reached by A[4]. Remember it. Consider DP-array as linked list, where value referred to previous position. So, prev = 13-2 = 11. We see, A[2] also included into the sum. remember "2". Prev position: prev = 11-7 = 4. See DP[4]. there is "0". remember [0], too. Prev = 4-4 = 0. We reached DP[0], stop interpretation. Thus, we collected remembered indexes in A[4,2,0].

问题已解决。

这篇关于如何在一个整数数组中找到相加为K的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！