20 初心与使命

1. 两数之和

前言

「算法题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 20 篇题解，更多题解关注 Somnia1337@力扣。

不忘初心，方能不辱使命。不知不觉间，这已经是「对话 Somnia」带给大家的第 20 篇题解了，一起用「Rust / Java / Python / Go」4 种语言回顾梦开始的地方吧！

题目描述

难度：🟢简单

标签：#数组哈希表

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

输入: nums=[2,7,11,15], target=9
输出: [0,1]
解释: 因为 nums[0]+nums[1]=9, 返回 [0, 1]

1. 暴力

双重 for 枚举每个数对，检查其和是否为 target。

Rust

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for i in 0..nums.len() {
            for j in i+1..nums.len() {
                if nums[i] + nums[j] == target {
                    return vec![i as i32, j as i32];
                }
            }
        }
        unreachable!()
    }
}

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }
}

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            for j in range(i + 1, len(nums)):
                if x + nums[j] == target:
                    return [i, j]

Go

func twoSum(nums []int, target int) []int {
    for i, x := range nums {
        for j := i + 1; j < len(nums); j++ {
            if x+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

2. 哈希表

哈希表记录 {值: 下标}，遍历 nums，对每个元素 x，检查其补数 target - x 是否存在，找到时返回两元素下标。

Rust

use std::collections::HashMap;
 
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut vis = HashMap::new();
        for (i, &x) in nums.iter().enumerate() {
            if let Some(&j) = vis.get(&(target - x)) {
                return vec![i as i32, j as i32];
            }
            vis.insert(x, i);
        }
        unreachable!()
    }
}

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> vis = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (vis.containsKey(target - nums[i])) {
                return new int[]{i, vis.get(target - nums[i])};
            }
            vis.put(nums[i], i);
        }
        return null;
    }
}

Python

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

Go

func twoSum(nums []int, target int) []int {
    vis := make(map[int]int)
    for i, x := range nums {
        if j, ok := vis[target-x]; ok {
            return []int{i, j}
        }
        vis[x] = i
    }
    return nil
}

最后

更多系列「外源推文」&「生活分享」关注公众号：