AcWing 1532. 找硬币 Java 双指针 + hash表
原题链接
简单
作者:
平头哥_0
,
2021-01-28 20:46:57
,
所有人可见
,
阅读 256
java 双指针 / hash表
双指针
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
boolean flag = false;
int n = sc.nextInt(), m = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < nums.length; i++) {
nums[i] = sc.nextInt();
}
Arrays.sort(nums);
for (int i = 0, j = nums.length-1; i < nums.length; i++) {
while(j>=0 && nums[i] + nums[j] > m)
j--;
if(j != -1 && j !=i && nums[i] + nums[j] == m){
flag = true;
System.out.printf("%d %d", nums[i], nums[j]);
return;
}
}
System.out.println("No Solution");
}
}
hash表
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
boolean flag = false;
int n = sc.nextInt(), m = sc.nextInt();
PriorityQueue<Integer>pq = new PriorityQueue<>();
int v1 = Integer.MAX_VALUE;
int v2 = -1;
for (int i = 0; i < n; i++) {
int x = sc.nextInt(), y = m - x;
if(pq.contains(y)){
pq.offer(x);
if(y<x){
int temp = x;
x = y;
y = temp;
}
v1 = Math.min(v1, x);
v2 = Math.max(v2, y);
}else{
pq.offer(x);
}
}
if(v1 != Integer.MAX_VALUE){
System.out.printf("%d %d", v1, v2);
}else{
System.out.println("No Solution");
}
return;
}
}