(暴力枚举) $O(n * m)$
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
//此题的逻辑代码
}
}
(双指针算法) $O(n + m)$
for(int i = 0, j = m - 1; i < n; i++) {
while(j >= 0 && a[i] + b[j] > x) j--;
//此题的逻辑代码
}
遇到双重循环计算复杂度时,其核心应该看当变量i自增后,j是从哪里开始计算的,分别来看这两段代码
在暴力求解下,当i自增后,j都是从零开始计算,所以在极端状况下,每一个j都要循环n次,在本题中,j的范围是0到m-1,则最多要循环(m-1) * n次
双指针算法下,j变量并不随i的变化,而重新回到最初的位置,因为在代码里我们并还没有在i自增后,重新将j初始化。这是两者最大的区别!!在极端情况下i走到n-1的位置时,j最多走了m-1次,所以总共花费为(n-1)+(m-1)
注意事项
此题很容易写错的一个关键条件就是 a[i] + b[j] > x 。很多同学可能会烦的错误就是将 > 写成 != 下面我们来举个例子分析
数组a:1 2 3 5
数组b:4 6 7 8
target = 6
假设现在i指向a中的第一个元素,j指向b中的最后一个元素,如果按照错误写法,j将指向b中的-1位置,由于我们采用的是双指针算法,j在i自增后并没有重新初始化,所以当i不管怎么自增,j依然指向-1这个没有意义的位置,此时造成本题无解。但其实a中的a和b中的4是符合题意的。这个点一定要注意!!!