impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
use std::collections::BTreeSet;
let mut rem = BTreeSet::new();
for (idx, &num) in nums.iter().enumerate() {
let prev = target - num;
if rem.contains(&prev) {
// Find prev index. Other way is to store index with value.
// But this fast O(N-i) check looks better for me.
for (prev_idx, &prev_num) in nums[..idx].iter().enumerate().rev() {
if prev_num == prev {
return vec![prev_idx as i32, idx as i32];
}
}
}
rem.insert(num);
}
unsafe {
std::hint::unreachable_unchecked();
}
}
}