Function leetcode_for_rust::cd0001_two_sum::two_sum

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32>

Solutions

Approach 1: One-pass Hash Table

• Time complexity: O(n)

• Space complexity: O(n)

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        if nums.len() < 2 {
            return vec![];
        }

        let mut positon = HashMap::new();
        for(i, num) in nums.iter().enumerate() {
            if positon.contains_key(num) {
                return vec![positon[num] as i32, i as i32];
            } else {
                positon.insert(target - num, i);
            }
        }

        return vec![];
    }
}

Approach 2: Brute Force

• Time complexity: O(n^2)

• Space complexity: O(1)

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        if nums.len() < 2 {
            return vec![];
        }

        let mut v: Vec<i32> = vec![];
        for i in 0..nums.len() {
            let n = target - nums[i];
            for j in (i+1)..nums.len() {
                if n == nums[j] {
                    v.push(i as i32);
                    v.push(j as i32);
                    return v;
                }
            }
        }

        v
    }
}