目标是创建一个接受两个参数的函数:整数数组和作为我们目标的整数，该函数应返回数组元素的两个索引，这些索引加起来等于目标。我们不能自行求和和元素，我们应该假设给定的数组始终包含和答案
我使用 for 循环和 while 循环解决了这个代码型练习。当 N 是数组的总元素时，for 循环的时间复杂度是线性 O(N)，但对于每个元素都有一个 while 过程，帽子也会线性增加。
这是否意味着这段代码的总时间复杂度是 O(N²) ？
public int[] twoSum(int[] nums, int target) {
int[] answer = new int[2];
for (int i = 0; i <= nums.length - 1; i++){
int finder = 0;
int index = 0;
while ( index <= nums.length - 1 ){
if (nums[i] != nums[index]){
finder = nums[i] + nums[index];
if (finder == target){
answer[0] = index;
answer[1] = i;
}
}
index++;
}
}
return answer;
}
您将如何优化时间和空间复杂性？
最佳答案
Does this means that the total time complexity of this code is O(N²) ?
是的，你的推理是正确的，你的代码确实是 O(N²) 时间复杂度。
How would you optimize this for time and space complexity?
您可以使用辅助数据结构，或者对数组进行排序，并对数组执行查找。
一个简单的解决方案(平均情况为 O(n))是使用哈希表，并在遍历列表时插入元素。然后，您需要在哈希表中查找 target - x，假设当前遍历的元素是 x。
我将实现留给您，我相信您可以做到并在此过程中学到很多东西!
关于java - 当需要嵌套循环时，如何提高空间和时间复杂度 Big(0)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/62742136/