hihocoder - towsum问题(三解)
描述
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。你需要输出这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。
你可以假设数组递增有序。
输入
第一行：N个整数，作为数组的元素，空格分开
第二行：target
输出
两个下标，空格隔开。如有多组满足要求，输出靠前的一组。
样例输入
4
2 7 11 15
9
样例输出
0 1
思路：
1.暴力法 O(n^2) （双重for循环，不多说了）
2.二分法O(nlgn)
当前数组元素x，和sum，转为对目标sum-x二分法寻找
3.双指针扫描法
头尾指针，向中间移动扫描。
（Java代码参考如下）
/**
* O(n^2) 暴力法
*/
import java.util.Scanner;
public class Exam12_00 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
int target = sc.nextInt();
for(int i = 0; i < arr.length; i++) {
for(int j = 0; j < arr.length; j++) {
int sum = arr[i] + arr[j];
if(sum == target&&i != j) {
System.out.println(i + " " + j);
return;
}
}
}
}
}
/**
* O(nlgn)
* 二分法变种
* 当前x 转为求 target - x 在递增数组中的位置 有则返回 两数小标
* 无则x 后移
*/
import java.util.Scanner;
public class Exam12_01 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
int sum = sc.nextInt();
for(int i = 0; i < arr.length ; i++) {
int target = sum - arr[i];
if(binaryRearch(arr, target)!= -1
&& i != binaryRearch(arr, target)) {// =-1没有找到
System.out.println(i + " " + binaryRearch(arr, target));
return;
}
}
}
static int binaryRearch(int[] arr, int target) {
int begin = 0;
int end = arr.length - 1;
while(begin < end) {
int midIndex = begin + ((end - begin)>>1);
if(arr[midIndex] > target) {
end = midIndex - 1;
}else if(arr[midIndex] < target) {
begin = midIndex + 1;
}else {
return midIndex;
}
}
return -1;
}
}
/**
* 双向指针扫描
**/
import java.util.Scanner;
public class Exam12_02 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for(int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
int target = sc.nextInt();
int head = 0;//头指针
int tail = arr.length-1;//尾指针
while(head < tail) {//没有找到
int sum = arr[head] + arr[tail];
if(sum > target) {
tail--;
}else if(sum < target) {
head++;
}else {
System.out.println(head + " " + tail);
return;
}
}
}
}
