leetcode

commit 25127541f47e5488aa0f6f79ca6180da42cf3921
parent e09dc5490831dca5c43d74c72b4d89fe6c849d4f
Author: ling0x <ling0x@users.noreply.github.com>
Date:   Sun, 12 Apr 2026 12:22:54 +0100

optimizations

Diffstat:
M
src/hash_table/two_sum.rs
 | 
36
++++++++++++++++++++++++------------
M
src/main.rs
 | 
10
+++++-----

2 files changed, 29 insertions(+), 17 deletions(-)
diff --git a/src/hash_table/two_sum.rs b/src/hash_table/two_sum.rs
@@ -1,5 +1,3 @@
-use std::collections::{HashMap, HashSet};
-
 use tracing::info;
 
 // First try - brute force approach without optimization
@@ -88,7 +86,7 @@ pub fn two_sum_5(nums: Vec<i32>, target: i32) -> Vec<i32> {
 // Without changing the array, can use additional space to speed up the search?
 // 65ms 2.54MB
 pub fn two_sum_6(nums: Vec<i32>, target: i32) -> Vec<i32> {
-    let mut map: HashMap<_, _> = nums.iter().enumerate().collect();
+    let mut map: std::collections::HashMap<_, _> = nums.iter().enumerate().collect();
     for (i1, x) in nums.iter().enumerate() {
         map.remove(&i1);
         let result = target - x;
@@ -100,13 +98,21 @@ pub fn two_sum_6(nums: Vec<i32>, target: i32) -> Vec<i32> {
 }
 
 pub fn two_sum_7(nums: Vec<i32>, target: i32) -> Vec<i32> {
-    let mut map: HashMap<_, _> = nums.iter().enumerate().collect();
-    for (i1, x) in nums.iter().enumerate() {
-        map.remove(&i1);
-        let result = target - x;
-        let position = map.iter().position(|(_, v)| v == &&result);
-        if let Some(i2) = position {
-            return vec![i1 as i32, i2 as i32];
+    let map: std::collections::HashMap<_, _> = nums.iter().enumerate().collect();
+    let reverse_map: std::collections::HashMap<_, _> =
+        nums.iter().enumerate().map(|(k, v)| (v, k)).collect();
+
+    for (i1, x) in map.iter() {
+        info!("{map:?}");
+        let result = target - *x;
+        if let Some(i2) = reverse_map.get(&result) {
+            info!(
+                "{} - {:?}(idx: {}) = {}(idx: {})",
+                target, x, i1, result, i2,
+            );
+            let res = vec![*i1 as i32, *i2 as i32];
+            info!("{res:?}");
+            return res;
         }
     }
     Vec::new()
@@ -115,7 +121,7 @@ pub fn two_sum_7(nums: Vec<i32>, target: i32) -> Vec<i32> {
 #[cfg(test)]
 mod tests {
     use crate::hash_table::two_sum::{
-        two_sum_1, two_sum_2, two_sum_3, two_sum_4, two_sum_5, two_sum_6,
+        two_sum_1, two_sum_2, two_sum_3, two_sum_4, two_sum_5, two_sum_6, two_sum_7,
     };
     use crate::test_utils::benchmark::{init_benchmark_tracing, run_and_assert_vec_any_order};
 
@@ -202,8 +208,14 @@ mod tests {
     }
 
     #[test]
-    // #[ignore]
+    #[ignore]
     fn two_sum_6_cases() {
         run_solver_cases("two_sum_6", two_sum_6, full_cases());
     }
+
+    #[test]
+    // #[ignore]
+    fn two_sum_7_cases() {
+        run_solver_cases("two_sum_7", two_sum_7, full_cases());
+    }
 }
diff --git a/src/main.rs b/src/main.rs
@@ -1,15 +1,15 @@
-use leetcode::hash_table::two_sum::two_sum_6;
+use leetcode::hash_table::two_sum::two_sum_7;
 use tracing::info;
 use tracing_subscriber::fmt;
 
 fn main() {
     fmt().with_target(false).compact().init();
     info!("-----------------------");
-    two_sum_6(vec![2, 7, 11, 15], 9);
+    two_sum_7(vec![2, 7, 11, 15], 9);
     info!("-----------------------");
-    two_sum_6(vec![3, 2, 3], 6);
+    two_sum_7(vec![3, 2, 3], 6);
     info!("-----------------------");
-    two_sum_6(vec![3, 2, 4], 6);
+    two_sum_7(vec![3, 2, 4], 6);
     info!("-----------------------");
-    two_sum_6(vec![-3, 4, 3, 90], 0);
+    two_sum_7(vec![-3, 4, 3, 90], 0);
 }