在Java中查找n个数组之间共同元素的总和

Question

我有一个程序，可以计算两个数组中相同元素的总和。为此，我使用了两个for循环，如果有三个数组，则可以使用三个for循环。但是如何计算n个数组中相同元素的总和，其中n在运行时确定。

我不知道如何在运行时更改循环次数，或者是否有其他相关概念可用？

以下是我尝试计算两个数组总和的代码：

import java.util.Scanner;

public class Sample {
    public static void main(String... args)
    {
        Scanner sc=new Scanner(System.in);
        int arr1[]={1,2,3,4,5},arr2[]={4,5,6,7,8},sum=0;
        for (int i=0;i<arr1.length;i++)
        {
            for (int j=0;j<arr2.length;j++)
            {
                if (arr1[i]==arr2[j])
                {
                    sum+=(arr1[i]);
                }
            }
        }
    }
}

- Bharat

---

你说：“共同元素”。如果你有三个数组：[1,2,3,4]，[2,3,5,6]和[2,5,6,8]...结果会是什么？ - x80486

结果为 2。 - RaminS

@Gendarme 不建议使用 int var[]。 - assylias

如果你有 {1,2,2} 和 {2,3,4}。它们的和应该是2还是4？（你的算法会得出4） - Flikk

应该是2。这是我的算法中的一个错误。 - Bharat

Answer 1

这可以有不同的实现方法。您可以使用以下方法。这是伪代码

1. 使用2D数组存储数组。如果数组数量为n，大小为m，则数组将为input[n][m]
2. 使用ArrayListcommonItems存储公共项。用input[0]的元素初始化它。
3. 现在遍历数组i = 1 to n-1。与每个input[i]比较，在每一步中仅存储commonItems和input[i]的公共项。您可以通过将input[i]转换为列表并使用retainAll方法来完成此操作。
4. 迭代结束时，commonItem列表将仅包含公共数字。现在对此列表的值进行求和。

- stinepike

---

我认为你应该从第三步开始使用i=1。第四步应该开始删除重复元素。 - bleistift2

Answer 2

假设元素的索引不重要：a[1]=2，a[5]=2，则只需要两个嵌套循环。首先，需要将 n-1 个数组放入一个集合列表中。然后遍历第n个数组，并检查每个元素是否存在于列表中所有集合中。如果存在，则加入总数中。

- efekctive

---

你的解决方案很好，但如何检查第n个数组的元素是否存在于剩余的n-1个数组中？ - Bharat

遍历集合列表的循环会告诉你这个答案。一旦你发现数组n中的一个元素没有命中这个列表中的任何一个元素，就跳出if语句，然后检查循环是否完成，如果是，则将其加入总数。 - efekctive

Answer 3

实际上有一种更通用的方法，也可以回答“如何在运行时更改循环次数”的问题。

通用问题

我们正在寻找一种实现类似于以下内容的方法：

for (i1 = 0; i1 < k1; i1++) { 
  for (i2 = 0; i2 < k2; i2++) {
    for (i3 = 0; i3 < k3; i3++) {
       ...
         for (in = 0; in < kn; in++) {
           f(x1[i1], x2[i2], ... xn[in]);
         }
       ...
     }
   }
 }

其中n在运行时给定，f是一个接受n个参数的函数，处理当前的n元组。

一般解决方案

有一个通用的解决方案，基于递归的概念。

以下是一种产生所需行为的实现：

void process(int idx, int n, int[][] x, int[] k, Object[] ntuple) {
    if (idx == n) {
        // we have a complete n-tuple, 
        // with an element from each of the n arrays
        f(ntuple);
        return;
    }

    // this is the idx'th "for" statement
    for (int i = 0; i < k[idx]; i++) {
        ntuple[idx] = x[idx][i];
        // with this recursive call we make sure that 
        // we also generate the rest of the for's
        process(idx + 1, n, x, k, ntuple);
    }
}

该函数假设n个数组存储在矩阵x中，第一次调用应该像这样：process(0, n, x, k, new Object[n]); 实际考虑到，上述解决方案具有较高的复杂度（O(k1⋅k2⋅..⋅kn)），但有时可以避免进入最深层循环。

事实上，在本文提到的特定问题中（需要对所有数组中的共同元素求和），我们可以跳过生成某些元组，例如如果已经x2[i2] ≠ x1[i1]。

在递归解决方案中，可以轻松地修剪这些情况。此问题的具体代码可能如下所示：

void process(int idx, int n, int[][] x, int[] k, int value) {
    if (idx == n) {
        // all elements from the current tuple are equal to "value". 
        // add this to the global "sum" variable
        sum += value;
        return;
    }

    for (int i = 0; i < k[idx]; i++) {
        if (idx == 0) {
            // this is the outer "for", set the new value
            value = x[0][i];
        } else {
            // check if the current element from the idx'th for
            // has the same value as all previous elements
            if (x[idx][i] == value) {
                process(idx + 1, n, x, k, value);
            }
        }
    }
}

- danbanica

---

非常感谢你...你能否提供一个最好的来源，从基础到高级学习递归？ - Bharat

欢迎！我稍微找了一下教程，但不确定该推荐哪一个。无论如何，我认为在从基础到高级的进阶过程中，你应该从像“递归阶乘”这样的简单程序开始，直到你感觉对自己调用函数感到舒适为止。然后你可以转向一些更高级的主题，比如“递归回溯”，用于解决诸如“N皇后”之类的问题。似乎有针对每个主题的教程，但我没有仔细看:) 如果你找不到任何这些主题的清晰解释，请告诉我。 - danbanica

谢谢您的回答，它肯定会帮助到我 :) - Bharat