Hash的应用，这个题目可以更加理解hash所换来的效率

本文主要是介绍Hash的应用，这个题目可以更加理解hash所换来的效率，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

Sum

Time Limit: 9000 MS Memory Limit: 65536 K

---

Sum

Mr. Jojer is given n numbers and an extra integer x, he wants to know whether there are two numbers whose sum is x.

Input

The input file contains several test cases. The first line of each test case contains two integers, n(<=1000001) and x. From the next line of each test case, there are n numbers.

Output

Each test case corresponds to a line in the output, which is either "YES" if there exists an answer or "NO" if not.

Sample Input

3 3
1 2 3
2 3
1 3

 

 

Sample Output

YES
NO

 

解题代码：

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n, sum; int num; int[] hash = new int[65537]; boolean flag; while(sc.hasNextInt()) { n = sc.nextInt(); sum = sc.nextInt(); flag = true; for(int i=0; i<n; i++) { num = sc.nextInt(); hash[num] = 1; } for(int i=0; i<hash.length/2+1; i++) { if(hash[i]==1 && hash[sum-i]==1) { System.out.println("YES"); flag = false; break; } } if(flag) { System.out.println("NO"); } } } }

 

用空间换取时间

这篇关于Hash的应用，这个题目可以更加理解hash所换来的效率的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---