Two Sum with a Map

Lab Java Intermediate 20 points

Read n integers and a target. Print the indexes i j (i < j) of the first pair (by j) that sums to the target, or none, in one pass with a HashMap.

Input

n, the integers, then the target.

Output

One line.

Example

Input

4
2 7 11 15
9

Output

0 1

Sample input available Sample output available

Editor

Java

Hints

For each value, look up target - value among the values seen so far.

Solution explanation

The map trades memory for speed: O(n) instead of O(n²).

Show solution

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int target = sc.nextInt();
        Map<Integer, Integer> seen = new HashMap<Integer, Integer>();
        String answer = "none";
        for (int j = 0; j < n; j++) {
            Integer i = seen.get(target - a[j]);
            if (i != null) {
                answer = i + " " + j;
                break;
            }
            if (!seen.containsKey(a[j])) {
                seen.put(a[j], j);
            }
        }
        System.out.println(answer);
    }
}

Output

Answer