LeetCode: 两数之和

首刷 LeetCode

规避版权问题，题目详见: 两数之和
仅在此备忘我的解题。

解题思路:

1. 遍历数组
2. 计算目标值与当前值的差值
3. 将 差值作为键在 map 中查找
4. 若找到，返回结果：map 对应的值和当前数组的索引值
5. 若未找到，则保存至 map：当前值作为键，当前索引作为值

以下为不同语言的实现。

Go 解题

func twoSum(nums []int, target int) []int {
    maps := make(map[int]int)
    
    for i := 0; i < len(nums); i++ {
        v := nums[i]
        diff := target - v
        if k, ok := maps[diff]; ok {
            return []int{k,i}
        }
        maps[v] = i
    }
    
    return []int{-1,-1}
}

执行用时: 4ms 内存消耗: 3.8MB

Jascript 解题

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map();
    for( i = 0; i < nums.length; i++){
        let diff = target - nums[i];
        
        if (map.has(diff)) {
            return [map.get(diff),i];
        }
        
        map.set(nums[i],i);
    }
    return [-1,-1];
};

执行用时: 64 ms 内存消耗: 35 MB

Python 解题

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dt = {}
        for i, n in enumerate(nums):
            diff = target - n
            if diff in dt:
                return [dt[diff], i]
            dt[n] = i

        return [-1,-1]

执行用时: 32 ms 内存消耗: 14.5 MB

Kotlin 解题

class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = hashMapOf<Int,Int>()
        for ((index,num) in nums.withIndex()){
            val diff = target - num
            if(map.containsKey(diff)){                     
                return intArrayOf(map[diff]!!,index) 
            }

            map[num] = index
        }

        return intArrayOf(-1,-1) 
    }
}

执行用时: 228 ms 内存消耗: 37.4 MB

Java 解题

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map <Integer,Integer> maps = new HashMap<>();

        for(int i = 0; i < nums.length; i++){
            int diff = target - nums[i];
            if (maps.containsKey(diff)) {
                return new int[]{maps.get(diff),i};
            }

            maps.put(nums[i],i);
        }

        return new int[]{-1,-1};
    }
}

执行用时：4 ms 内存消耗：41.6 MB

Rust 解题

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        use std::collections::BTreeMap;

        let mut maps: BTreeMap<i32, usize> = BTreeMap::new();
        let mut result: Vec<i32> = vec![-1; 2];

        for (k, v) in nums.iter().enumerate() {
            let diff = target - v;
            if maps.contains_key(&diff) {
                let get_v = *maps.get(&diff).unwrap();
                result[0] = get_v as i32;
                result[1] = k as i32;
                break;
            }
            maps.insert(*v, k);
        }
        result
    }
}

执行用时：0 ms 内存消耗：2.4 MB

测试结果是解题后由 LeetCode 给出，供参考