返回两个数字的索引，使它们相加到一个特定的目标

Question

我想解决以下问题：

给定一个整数数组，返回两个数字的索引，使它们相加到一个特定的目标。

我将下面的数组作为输入-[2,7,11,15]，目标为9。

因为nums[0]nums[1]=27=9，所以返回[0，1]。

这是我的密码-

import java.util.Random;

public class TwoSum {

    static int[] numbers = new int[] {2, 7, 11, 15};
    int[] indices = new int[numbers.length];

    public static int[] returnIndices(int target, int[] inputArr) {
        int[] indices = new int[2];
        int randomOne = new Random().nextInt(inputArr.length);
        int randomTwo = new Random().nextInt(inputArr.length);
        while(true) {
            if(target == inputArr[randomOne] + inputArr[randomTwo]) {
                indices[0] = randomOne;
                indices[1] = randomTwo;
                break;
            }
        }
        System.out.println("done");
        return indices;
    }

    public static void main(String[] args) {
        int[] output = returnIndices(9, numbers);
    }

}

这是解决我问题的正确方法吗？

Answer 1

我在c#中试过，可能会有帮助。。

class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            int[] nums = { 2, 7, 11, 15 };
            int target = 9;
            int[] result= TwoSumNumbers(nums, target);
        }

        public static int[] TwoSumNumbers(int[] nums, int target)
        {
            Dictionary<int, int> numsDict = new Dictionary<int, int>();

            for (int i = 0; i < nums.Length; i++)
            {
                int num = nums[i];

                if (numsDict.TryGetValue(target - num, out int index))
                {
                    return new[] { index, i };
                }

                numsDict[num] = i;
            }

            return null;
        }
    }

Answer 2

解决这个问题有多种方法：

1. Hashmap-way-@mettleap-answer已经涵盖了这个问题。

让我们先举一个例子来看看它的实际应用。我们得到了数组中的arr=[5,2,1,9,7]元素，如果我们能得到8，我们将找到两个元素的索引。

如果你仔细观察，你就会知道如果我们对数组中最后三个元素求和，我们将得到8，这意味着2和4将是我们的答案。那么那里的土地会是怎样的呢？让我们一步一步走

>

维护一个相同大小的单独数组，它将在初始设置中保存arr的索引。

[5, 2, 1, 9, 7] = arr
[0, 1, 2, 3, 4] = index_arr

现在，按递增顺序对arr进行排序，并对索引\u arr进行排序，以便初始设置中arr中的元素索引仍然存在。

[1, 2, 5, 7, 9] = arr
[2, 1, 0, 4, 3] = index_arr

使用下面的伪代码：

low  = 0
high = length of arr - 1

while (low < high) {
    sum = arr[low] + arr[high]

    if (sum  == number) {}
        print "index_arr[low]" and "index_arr[high]" 
        break the loop and exit
    } else if ( sum < number ) {
        low = low + 1
    } else {
        high = high - 1
    }
}

让我们看看psuedo代码的实际应用：

[1, 2, 5, 7, 9] = arr
[2, 1, 0, 4, 3] = index_arr

Iteration # 01
low = 0 and high = 4
sum = arr[0] + arr[4] = 1 + 9 = 10
10 > 8 , means 'else' will be executed high = high - 1 = 4 - 1 = 3

Iteration # 02
low = 0 and high = 3
sum = arr[0] + arr[3] = 1 + 7 = 8
8 == 8 , means first 'if' condiion will execute, and will indices and exit the loop

时间复杂度-O（n）
空间复杂度-O（n）

Answer 3

您可以使用hashmap以以下方式存储第一个数组：

   key  value(index in array)
    2 - 0
    7 - 1
    11 - 2
    15 - 3

接下来获取目标元素9，并开始从索引0遍历给定数组。

索引0处的元素为2--

附加说明：您需要处理以下情况：

arr=[3,2,1,1]target=6（本例中不存在答案，但通过上述方法，当您计算6-3=3时，您会得到索引0作为答案。）

但这可以通过检查（target arr[i]==arr[i]）是否返回true来轻松解决。如果返回true，并且hashmap在键arr[i]处存储了两个索引，则将其作为答案返回，否则继续下一个元素。