AcWing 1532. 找硬币Java哈希表+双指针详细注释
原题链接
简单
作者:
长街听风
,
2021-01-25 19:47:20
,
所有人可见
,
阅读 303
哈希表
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int v1 = Integer.MAX_VALUE;//先给v1设置一个很大的数,超出题目的数据范围,方便后续对其更新
int v2 = -1;
Set<Integer> set = new HashSet<>();
for(int i = 0;i < n;i++){
int x = scanner.nextInt();
int y = m - x;
if(set.contains(y)){//找到了一组解
set.add(x);//将当前数加入集合set
//(x,y)是一组解,我们要找到里面较小的值去和v1比较,这里让x保存这组解中较小的数
if(x > y){
int temp = x;
x = y;
y = temp;
}
if(x < v1){//看看是否需要更新最终的解(v1,v2)
v1 = x;
v2 = y;
}
}else{
set.add(x);//将当前数加入集合set
}
}
if(v1 != Integer.MAX_VALUE){//v1被更新过,说明肯定找到了至少一组解
System.out.println(v1 + " "+ v2);
}else{
System.out.println("No Solution");
}
}
}
双指针
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n];
for(int i = 0;i < n ;i++){
arr[i] = scanner.nextInt();
}
//使用双指针前,基本都需要先对数组进行排序,即要求数组是有序的,之后才好根据情况移动左右指针
Arrays.sort(arr);
int l = 0,r = n - 1;
while(l < r){
if(arr[l] + arr[r] > m){
r--;
}else if(arr[l] + arr[r] < m){
l++;
}else{//首次找到一组arr[l]+arr[r] = m时,即是最终的的结果,因为arr是有序的,所以找到的第一组解就是v1最小的那组,可以break退出while循环了
break;
}
}
if(l < r){//退出上面的while循环后,还有l < r,说明是找到了解后break退出的
System.out.println(arr[l] + " " + arr[r]);
}else{
System.out.println("No Solution");
}
}
}