【HackerRank】Ice Cream Parlor
Sunny and Johnny together have M dollars which they intend to use at the ice cream parlour. Among N flavors available, they have to choose two distinct flavors whose cost equals M. Given a list of cost of N flavors, output the indices of two items whose sum equals M. The cost of a flavor (ci) will be no more than 10000.
Input Format
The first line of the input contains T, T test cases follow.
Each test case follows the format: The first line contains M. The second line contains the number N. The third line contains N single space separated integers denoting the price of each flavor ci.
Output Format
Output two integers, each of which is a valid index of the flavor. The lower index must be printed first. Indices are indexed from 1 to N.
Constraints
1 ≤ T ≤ 50
2 ≤ M ≤ 10000
2 ≤ N ≤ 10000
1 ≤ ci ≤ 10000
The prices of two items may be same and each test case has a unique solution.
又是一个求数组中两个数和正好是m的问题,类似leetcode中的Two Sum问题。
只是在这个问题中,数组中的数是有可能重复的,所以map中的value要用一个arrayList保存。
另外注意找的时候要保持i比在map中找到的坐标小(如代码26行的判断所示),以免重复。
代码如下:
import java.util.*; public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while(t-- >0){
int m = in.nextInt();
int n = in.nextInt();
int[] prices = new int[n];
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>(); for(int i = 0;i < n;i++){
prices[i]=in.nextInt();
if(!map.containsKey(prices[i]))
map.put(prices[i], new ArrayList<Integer>());
map.get(prices[i]).add(i);
} for(int i = 0;i < n;i++){
int has = prices[i];
int toFind = m-prices[i]; if(map.containsKey(toFind)){
for(int temp:map.get(toFind)){
if(i < temp){
System.out.printf("%d %d",i+1,temp+1);
System.out.println();
}
}
}
}
}
}
}
最新文章
- 阿里云服务器上开启linux远程桌面连接
- 网页中插入外部视频的几种方法(PC与手机网页通用)
- 一个Java内存可见性问题的分析
- [Letcode] 1. Two Sum
- XML序列化成对象
- iPad accessory communication through UART
- Android正在使用Handler实现信息发布机制(一)
- 文件搜索神器 Everything
- JVM基础02-class文件
- 【T-SQL进阶】02.理解SQL查询的底层原理
- sql server系统存储过程大全
- Codeforce 835A - Key races
- 2019/3/19 wen 运算符
- spring: beanutils.copyproperties将一个对象的数据塞入到另一个对象中(合并对象)
- tensorflow读取训练数据方法
- jqGrid资源
- [shell]简单的shell提示和参数脚本
- 2-JRE System Libraty [eclipse-mars](unbound)
- oracle-02 用户管理
- ajax和json数据