增加数量以满足可能的目标

Question

我已经解决了一个问题，从数组中添加两个数字来获得目标数字。非常基本，场景如下:

输入>:

arr = [2, 4, 6, 10]
Target = 10

:检索到的索引

arr = [1, 2] //As 4 + 6 = 10

<<p>代码片段/strong>:

public int[] GetTarget(int[] nums, int target)
{
List<int> lst = new List<int>(); //List to save number indexes
int[] newArr = null; //Array initialization
for (int i = 0; i < (nums.Length - 1); i++) //First loop to iterate numbers from 0 index
{
for (int j = (i + 1); j < nums.Length; j++) //Second loop to iterate numbers from 1 index
{
if (nums[i] + nums[j] == target) //Check target is met adding numbers iterating the loops
{
lst.Add(i); //Save indexes here
lst.Add(j);
newArr = lst.ToArray(); //Convert the list to array
}
}
}
return newArr;
}
}

所以上面的代码工作得很好，它的时间复杂度是O(n²)，因为它使用两个循环迭代结果集。我想知道我是否可以使用一个循环或任何替代方法来减少迭代。

还有一件事，我使用list来保存数字的索引如下:

List<int> lst = new List<int>(); //List to save number indexes

是否有任何方法，我可以实现上述不使用列表(虽然内部使用动态数组)，并使用数组保存这些索引?

arr[i] = index;

Answer 1

您可以用以下循环替换您的for循环。我不认为列表需要保存这些索引。您可以在找到索引后简单地返回它们。

在你的代码中，你所做的是，你迭代整个数组，即使你的索引被找到。

for(int i = 0; i < arr.Length - 1; i++){
for(int j = i + 1; j < arr.Length; j++){
if(arr[i] + arr[j] == target){
return new arr[]{i,j};
}
}

解决这个问题的另一种方法是使用Dictionary。其中键将是arr[i]，值将是索引(i)。时间复杂度在最坏情况下为O(n)。

// Initialise a Dictionary
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int i = 0; i<=arr.Length; i++){

// Check if (target - arr[i]) exists in dict
if(dict.ContainsKey(target - arr[i])){
//if it exists, return value and i;
return new int[]{dict[target - arr[i]], i};
} 
else
{
// otherwise add arr[i] to the dict to iterate further
dict[arr[i]] = i;
}
}