首页 > 代码库 > 【HackerRank】Ice Cream Parlor

【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行的判断所示),以免重复。

代码如下:

 1 import java.util.*; 2  3 public class Solution { 4     public static void main(String[] args) { 5         Scanner in = new Scanner(System.in); 6         int t = in.nextInt(); 7         while(t-- >0){ 8             int m = in.nextInt(); 9             int n = in.nextInt();10             int[] prices = new int[n];11             HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();12             13             for(int i = 0;i < n;i++){14                 prices[i]=in.nextInt();15                 if(!map.containsKey(prices[i]))16                     map.put(prices[i], new ArrayList<Integer>());17                 map.get(prices[i]).add(i);18             }19             20             for(int i = 0;i < n;i++){21                 int has = prices[i];22                 int toFind = m-prices[i];23                 24                 if(map.containsKey(toFind)){25                     for(int temp:map.get(toFind)){26                         if(i < temp){27                             System.out.printf("%d %d",i+1,temp+1);28                             System.out.println();29                         }30                     }31                 }32             }33         }       34     }35 }