java - 降低程序的复杂性

Question

如何降低此代码的复杂性：如果数组中有两个元素的和等于数字 K，则此代码返回 true

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;
}

标签： javatime-complexity

Answer 1

作为选项之一，您可以使用Set存储以前的号码。它将时间复杂度从O(n*n)降低到O(n)，但同时将空间复杂度从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;
}