题目解析
这类题目很常见,遇到求和问题就可以考虑用双指针算法来试一试
- 设置两个指针i,j,一个在数组前面,一个在最后,先对数组从小到大进行排序
- 如果值加起来大于目标值的话,我们要想办法把值变小,也就是让j指针向前走,j–
- 如果值加起来小于目标值的话,我们要想办法把值变大,也就是让i指针向后走,i++
- 如果值加起来相等的话,就可以输出结果了
Java代码
import java.util.Scanner;
import java.util.Arrays;
public class Main{
static int N = 100010;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] a = new int[n];
for(int i = 0; i < n; i ++) a[i] = in.nextInt();
Arrays.sort(a); //对a数组进行排序
for(int i = 0, j = n - 1; i < n; i ++)
{
while(j >= 0 && a[i] + a[j] > m) j--;
if(i != j && a[i] + a[j] == m)
{
System.out.print(a[i] + " " + a[j]);
break; //因为只输出一个解,所以找到就可以break了
}
else if(i >= j)
{
System.out.print("No Solution");
break;
}
}
}
}