降低程序的复杂性

Question

如何降低这段代码的复杂性：此代码 returns 如果数组中有两个元素的和等于数字 K

则为真

public static boolean methode(int c, int[] t) {
    for(int i = 0; i < t.length; i++)
        for(int j = 0; j < t.length; j++)
            if(j != i && t[i] + t[j] == c)
                return true;

    return false;
}

Answer 1

作为选项之一，您可以使用Set来存储以前的数字。它将时间复杂度从 O(n*n) 降低到 O(n)，但同时增加了 space 复杂度从 O(1) 到 O(n).

public static boolean verification(int k, int[] tab) {
    Set<Integer> unique = new HashSet<>();
    
    for(int i = 0; i < tab.length; i++) {
        if(unique.contains(k - tab[i]))
            return true;

        unique.add(tab[i]);
    }

    return false;
}

Answer 2

如果你想检查两个元素的总和，那么你可以使用下面的代码。简单一点:

public static boolean verification(int k, int[] tab) {
    for(int i = 0; i < tab.length - 1; i++)
        for(int j = i + 1; j < tab.length; j++)
            if(tab[i] + tab[j] == k)
                return true;

    return false;
}

降低程序的复杂性

Reduce the complexity of a program

java

time-complexity