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 }