题目:Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X.
直接的方法:双层循环解决,复杂度O(n2)。
two-pointer: 两个指针l和r,一前一后的跑,O(n)解决。
int l, r;
l = 0, r = n-1;
while(l<r) {
if(a[l]+a[r]<X) {
++l;
}else if(a[l] + a[r] == X) {
// found
break;
}else {
--r;
}
}
特点: 一般来说,two-pointer夹着的是一类,一般类和类之间相接,若是类与类间隔几个相邻,则不能使用two-pointer,要dp。
参考:
https://www.geeksforgeeks.org/two-pointers-technique/