当需要嵌套循环时，如何改进 space 和时间复杂度 Big(0)？

Question

objective 是创建一个函数，它接受两个参数：整数数组和一个整数是我们的目标，该函数应该 return 将数组元素的两个索引相加达目标。我们不能自己求和和元素，我们应该假设给定的数组总是包含并回答

我使用 for 循环和 while 循环解决了这个代码套路练习。当 N 是数组的总元素时，for 循环的时间复杂度是线性的 O(N) 但是对于每个元素都有一个 while process hat 也线性增加。

这是否意味着这段代码的总时间复杂度是 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;
        
    }

您将如何针对时间和 space 复杂性对其进行优化？

Answer 1

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) 一般情况，是使用散列 table，并在遍历列表时插入元素。然后，您需要在哈希 table 中查找 target - x，假设当前遍历的元素是 x.

我将实施留给您，我相信您可以做到并在此过程中学到很多东西！

当需要嵌套循环时，如何改进 space 和时间复杂度 Big(0)？

How can you improve the space and time complexity Big(0) of when nested loops are needed?

java

algorithm

big-o

time-complexity

nested-loops