3个嵌套循环的时间复杂度计算

Question

我正在尝试提高算法技能。我有一个非常简单的代码。

Qs：查找等于0的所有三元组（非重复）。

我认为时间复杂度为O（nlogn），与嵌套循环（n ^ 3）无关。我的理由是：可以说

nums长度=3。然后代码运行1次。 {-1,0,-1}。numslength =3。然后代码运行1次。 {-1,0,1,2}然后代码运行3次。 -1,0,1，01,0,2，-1,1,2。

类似地，当长度为5时，代码运行6次[] [] [] [] [] []，而对于长度7，它运行9次。

因此似乎要考虑的三元组数量增加了3(n-2)，其中3<=n。因此，时间复杂度为n，因为3n-6〜n。

但是因为我有Arrays.sort，所以时间复杂度变为O(nlogn)。

我在俯视什么？

int[] nums = { -1, 0, 1, 2, -1, -4};
List<List<Integer>> test = new ArrayList<List<Integer>>();
nums = new int[] { -1, 0, 1};
Arrays.sort(nums);
HashSet<String> duplicates = new HashSet<String> ();

for (int i = 0 ; i < nums.length - 2 ; i++) { //i->0 - 3
    for (int j = i + 1; j < nums.length - 1; j++) { // j -> 1-4
        for (int k = j + 1; k < nums.length; k++) { //k ->2-5

            String sInt = nums[i] + "" + nums[j] + "" + nums[k];

            if ((nums[i] + nums[j] + nums[k]) == 0 && !duplicates.contains(sInt)) {
                ArrayList<Integer> t = new ArrayList<Integer> ();
                t.add(nums[i]);
                t.add(nums[j]);
                t.add(nums[k]);
                test.add(t);
            }

            duplicates.add(sInt);
        }
    }
}

return test;

Answer 1

有n*(n-1)(n-2)/6个三元组，并且代码检查每个]]。时间复杂度为O(n^3)。我看不到Arrays.sort()的相关性。

Answer 2

似乎您正在解决3Sum problem of LeetCode (15)