use std::collections::HashMap;

fn print_pairs(arr: &[i32], target: i32) {
    let mut counts = HashMap::with_capacity(arr.len());

    for x in arr {
        let y = target - x;
        if let Some(count) = counts.get(&y).copied() {
            for _ in 0..count {
                //                println!("{} + {} = {}", y, x, target);
            }
        }
        *counts.entry(x).or_insert(0) += 1;
    }
}

use std::cmp::Ordering;

fn sort_print_pairs(arr: &mut [i32], target: i32) {
    arr.sort();
    let mut i = 0;
    let mut j = arr.len() - 1;
    while i < j {
        let sum = arr[i] + arr[j];
        match sum.cmp(&target) {
            Ordering::Less => i += 1,
            Ordering::Greater => j -= 1,
            Ordering::Equal => {
                //                println!("{} + {} = {}", arr[i], arr[j], target);
                i += 1;
                j -= 1;
            }
        }
    }
}

use std::time::Instant;

fn main() {
    let now = Instant::now();
    let mut input: Vec<_> = (50_000 - 4_200_000..50_000).collect();
    println!("vec creation: {:?}", now.elapsed());

    let target = 6;

    let now = Instant::now();
    print_pairs(&input, target);
    println!("print_pairs: {:?}", now.elapsed());

    println!("");

    let now = Instant::now();
    sort_print_pairs(&mut input, target);
    println!("sort_print_pairs: {:?}", now.elapsed());
}