两数之和

发表于
本文字数： 761 阅读时长 ≈ 1 分钟

LeetCode每日一题，1. Two Sum

先看题目描述

大意就是给定一个整数数组 nums 和一个目标数 target，让我们返回 nums 中相加等于 target 的两个数的下标

算法和思路

哈希表

思路就是使用哈希表，遍历一次 nums 数组即可

每遍历到一个数字 num 时，进行判断：

  • 若哈希表的 key 中存在 num，则直接将该 key 值对应的 value 和这个 num 对应的下标返回
  • 否则，则计算 tar = target - num，将 tar 与 num 对应的下标存入哈希表中

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.HashMap;

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

            }
            int tar = target - num;
            map.put(tar, i);
        }
        return new int[2];
    }
}