在计算机领域,算法是一个永恒的主题。任何计算机使用者都希望计算机能运行得更快一些或是能解决更大规模的问题。从现在开始,跟随我每天刷一道算法题吧!


LeetCode #1 两数之和

题目

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

题目要求:在数组中找到两个元素的索引,且这两个元素相加等于目标值。

思路:
在数组中找出两个元素。我们第一时间就可以想到使用两层循环进行查找,外循环寻找第一个元素,内循环寻找第二个元素。
但是,这种方法的效率非常低。在这一道题中,我们主要的任务是,也就是遍历。
所以我们需要一种比较快速的遍历方法,那就是 map.containsKey() 方法。

我们用 map.containsKey() 方法代替内循环的查找工作。

  1. for循环遍历每一个元素,在map中查找与该元素符合条件的元素。

  2. 如果map中没有符合条件的元素,则将该元素放入map中。

  3. 为下一个元素寻找符合条件的元素。

一遍哈希遍历代码:

public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int length = nums.length;

for(int i = 0; i < length; i++){
int value = target - nums[i];
// 如果 map 存在此差值,则返回
if(map.containsKey(value)){
return new int[]{i, map.get(value)};
}
// 将该数组的值存入 map
map.put(nums[i], i);
}
return null;
}

评论