二分查找 O(nlogn) AC
思路:
因为两个数组均为有序数组A和B,目标是寻找两数之和等于给定值target
故可以遍历一个数组A,在数组B中使用二分查找,在O(logn)的时间复杂度寻找
二分查找技巧
二分查找写法很多,这里推荐一个我最常用的一种,半开半闭,即 [) 或 (]
这里使用哪种区间和你维护的区间有关系,( 表示这个值取不到
二分结束条件: while (l + 1 < r) => 当l + 1 = r 时 结束,表示区间只有一个元素
return的值是]的值,但是可能存在找不到的情况,所以根据题意要去特判一下
mid = (l + r) / 2
写法1:
private int[] solve(int[] a, int[] b, int x) {
int[] ans = new int[2];
ans[0] = -1; ans[1] = -1;
for (int i = 0; i < a.length; i++) {
int t = x - a[i];
int l = -1, r = b.length;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (b[mid] > t) {
r = mid;
} else {
l = mid;
}
}
if (l != -1 && b[l] == t) { ans[0] = i; ans[1] = l; }
}
return ans;
}
写法2:
private int[] solve(int[] a, int[] b, int x) {
int[] ans = new int[2];
ans[0] = -1; ans[1] = -1;
for (int i = 0; i < a.length; i++) {
int t = x - a[i];
int l = 0, r = b.length;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (b[mid] > t) {
r = mid;
} else {
l = mid;
}
}
if (b[l] == t) {
ans[0] = i; ans[1] = l;
break;
}
}
return ans;
}
哈希表 O(n) AC
想要快速找到一个数组A中是否存在某一个元素,可以利用哈希表预处理下,map.put(key, val)
key:A[i], val:i
private int[] solve(int[] a, int[] b, int x) {
int[] ans = new int[2];
ans[0] = -1; ans[1] = -1;
HashMap<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < b.length; i++) hash.put(b[i], i);
for (int i = 0; i < a.length; i++) {
int t = x - a[i];
if (hash.containsKey(t)) {
ans[0] = i;
ans[1] = hash.get(t);
break;
}
}
return ans;
}
双指针 O(n) AC
这个一开始没想到怎么做,看了大佬的题解后,才大致明白
数组A:从左到右枚举 (用i表示下标)i只会一直向右移动
数组B:从右到左枚举 (用j表示下标)j只会一直向左移动
private int[] solve(int[] a, int[] b, int x) {
int[] ans = new int[2];
ans[0] = -1; ans[1] = -1;
int n = a.length, m = b.length;
for (int i = 0, j = m - 1; i < n; i++) {
while (j >= 0 && a[i] + b[j] > x) j--;
if (j >= 0 && a[i] + b[j] == x) { ans[0] = i; ans[1] = j; break; }
}
return ans;
}