如何实现双和（无哈希 - 仅使用我的数组代码）？

Question

我正在尝试使用 Eclipse 做一个二和问题。我想使用一个数组并让程序执行标准递归以查看下面列出的数组中的任何整数是否可以加在一起等于我的目标总和 9。

这是我正在解决的问题，在实施我的策略时遇到了麻烦......（注意我已经尝试过对我的编码进行多种解释）

给定一个整数数组，返回两个数字的索引，使它们加起来等于一个特定的目标。

您可能会假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。

例子：

给定 nums = [2, 7, 11, 15], target = 9,

因为 nums[0] + nums[1] = 2 + 7 = 9，返回 [0, 1]。

import java.util.ArrayList;

public class twoSumArray {

    public twoSumArray(int[] nums, int target) 

    {

        for(int i = 0; i < nums.length; i++) 

        {

            for (int j = i + 1; j < nums.length; j++) 

            {

                if (nums[j] == target - nums[i]) 

                {

                }

            }

        }

    }   

    public static void main(String[] args) {

        ArrayList<Integer>myArray = new ArrayList<Integer>();

        myArray.add(2);

        myArray.add(7);

        myArray.add(11);

        myArray.add(15);

        int target = 9;

        ArrayList<Integer> result = twoSum(myArray,target);

        for(int j : result)

            System.out.print("["+j+","+target+"]");

    }

}

我试过的另一个代码......

class Solution {

    public static int[] twoSum(int[] nums, int target) 

    {

        for(int i = 0; i < nums.length; i++) 

        {

            for (int j = i + 1; j < nums.length; j++) 

            {

                if (nums[j] == target - nums[i]) 

                {

                    return new int[] {i, j};

                }   

            }

        }

        System.out.println(twoSum.Solution);

    }

    public static void main(String[] args) {

        int[] nums = {2,7,11,15};

        twoSum(nums , 9);

    }

}

Answer 1

您的代码中存在一些语法错误。为了简洁起见，我将发布一个您要实现的目标的最小示例。没有散列，你不会得到下面运行的答案O(n^2)但是，您可以获得 aO(n^2)而无需散列（您的第二个解决方案实际上在逻辑上是正确的，但在语法上是错误的。）例如，您为什么要打印System.out.println(twoSum.Solution);？你打电话twoSum(nums , 9);但你从来没有真正打印结果。public class TwoSum {&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; int[] answer = twoSum(new int[]{1, 2, 3}, 4);&nbsp; &nbsp; &nbsp; &nbsp; if (answer != null)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println("[" + answer[0] + ", " + answer[1] + "]");&nbsp; &nbsp; }&nbsp; &nbsp; public static int[] twoSum(int[] numbers, int target) {&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < numbers.length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (int j = i + 1; j < numbers.length; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (numbers[i] + numbers[j] == target) return new int[]{ i, j };&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // no answer&nbsp; &nbsp; &nbsp; &nbsp; return null;&nbsp; &nbsp; }}这个解决方案通常不受欢迎，因为它不是最有效的，而且是一种蛮力算法。但是，它非常简单，不需要太多思考就可以理解。

Answer 2

您确实要求递归解决方案。所以这可行，但它确实需要为vals数组提供起始索引。&nbsp; &nbsp; int[] vals = { 1, 2, 7, 9, 5, 3, 10};&nbsp; &nbsp; System.out.println(Arrays.toString(twoSum(vals, 0, 1, 15)));&nbsp; &nbsp; public static int[] twoSum(int[] v, int n, int m, int target) {&nbsp; &nbsp; &nbsp; if (n == v.length) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return new int[] { -1, -1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;};&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; if (m == v.length) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return twoSum(v, n + 1, n + 2, target);&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; if (v[n] + v[m] == target) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return new int[] { n, m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;};&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; return twoSum(v, n, m + 1, target);&nbsp; &nbsp; }[-1,-1]如果找不到总和，它会返回一个数组。您还可以返回一个空数组甚至null.这应该很容易理解。它基本上像两个嵌套循环一样工作，递增n并m适当地检查invariants以确保索引不等于数组长度。但是，如果您只想要一个行为完全相同的普通旧嵌套循环解决方案，您可以执行以下操作：&nbsp; &nbsp;public static int[] twoSum(int[] v, int target) {&nbsp; &nbsp; &nbsp; for (int n = 0; n < v.length - 1; n++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for (int m = n + 1; m < v.length; m++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (v[n] + v[m] == target) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return new int[] { n, m&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;};&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; return new int[] { -1, -1&nbsp; &nbsp; &nbsp; };&nbsp; &nbsp;}

Answer 3

我意识到我迟到了这个讨论 - 但是是的，你可以在线性时间内解决“双和”而不用散列（仅使用标准数组），前提是你的所有源值都是非负的（即使那样，有一些巧妙的解决方法 - 请参阅此答案的底部）。诀窍是声明一个布尔数组，其容量等于源数组中的最大值（警告） *。或者，如果您想避免对数组进行额外的线性时间扫描以获得其最大值，并且您不介意使用额外的空间，只需将容量设置为最大允许的数组容量（在我的语言中使用，C#，是2147483591）：// Some test input data:var target = 11;var arr = new[] { 1, 2, 7, 9, 5, 3, 10 };// complements array:var complements = new bool[2147483591];当数组声明为容量时，其值将自动填充给定数据类型的默认值，对于布尔值是false.现在只需单次遍历源数组以查看数组中complements位置处的元素compIndex（即target减去当前数组元素）是否设置为true.如果是这样，将(num, compIndex)元组添加到结果集中。否则，将处的元素的值设置complements为。truenum这是整个功能：IEnumerable<(int, int)> TwoSum(int[] arr, int target){&nbsp; &nbsp; var foundResults = new List<(int, int)>();&nbsp; &nbsp; var complements = new bool[2147483591] // or arr.Max() but be careful of overflow;&nbsp; &nbsp; foreach (var num in arr)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; var compIndex = target - num;&nbsp; &nbsp; &nbsp; &nbsp; if (complements[compIndex])&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; foundResults.Add((num, compIndex));&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; complements[num] = true;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return (foundResults.Any() ? foundResults : new[] { (-1, -1) });}void Main(){&nbsp; &nbsp; var target = 10;&nbsp; &nbsp; var arr = new[] { 1, 2, 7, 9, 5, 3, 10 };&nbsp; &nbsp; TwoSum(arr, target);&nbsp; &nbsp; // returns [{9, 1},{3, 7}]}上面的 C# 代码可以很容易地翻译成 C、Java、JavaScript 等。（警告） * 如果您的源数组包含的值大于布尔数组的最大容量，则有多种方法可以解决此问题（在 Google 上搜索与BigArray<T>您选择的语言相关的实现）。同样，如果您必须考虑源数组中的负数，也有创造性的方法来解决这个问题。例如，使您的complements布尔数组成为布尔2 元组数组而不是标量（即标记给定数字的正负版本是否存在的值）。（请注意，在现实生活中，我会简单地使用基于哈希的解决方案，而不是经历所有这些麻烦。但我已经包含了这个答案，以防万一您在与非常严格的招聘经理的面试中遇到这个问题:-)）。

Answer 4

您需要使用 gready 方式执行此操作，您开始对最大（结果）以下的任何数字序列求和每次选择似乎是最佳选择的数字（最佳选择意味着它与前一个总和的总和不大于所需的结果）并且不重复地强制执行此操作，直到您获得所有可能的组合或使用回溯返回当你溢出结果并测试其他组合选项时的步骤数这比简单的天真的野蛮力方法要快得多，如果我给你一个足够大的数组，那将不得不测试 nlog(n) 组合那是不真实的编辑：我注意到在评论后它添加了两个数字而不是一个集合然后它更简单首先蛮力天真的方法是最糟糕的因为除了操作等式中数字的位置并不重要所以你测试每个数字通过右边的下一个数字直到 N-1 它的 N*2-1 可比较而不是 N^2 在 niave force