两数之和(简单)
1. 题目描述
给定一个整数数组
nums和一个目标值target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
-
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
2. 个人解题思路~暴力法
- 使用嵌套循环遍历数组中每个元素
- 再进行两两比较看是否等于目标值
- 返回结果
class Solution {
public int[] twoSum(int[] nums, int target) {
// 遍历数组获取每一个元素
for (int i = 0; i < nums.length; i++) {
// 遍历数组 i 后的所有元素
for (int j = i + 1; j < nums.length; j++) {
// 判断该值是否等于目标值减去 i 元素
if (nums[j] == target - nums[i]) {
// 符合条件返回两个元素所在位置索引值
return new int[] { i, j };
}
}
}
// 如果没有符合条件,给出参数不正确的异常提示信息
throw new IllegalArgumentException("No two sum solution");
}
}
提交结果:
两数之和(简单)-暴力法.png
3. 官方解题思路~一遍哈希表
class Solution {
public int[] twoSum(int[] nums, int target) {
// 新建一个键值对对象保存数组中每位元素与对应的索引值
Map<Integer, Integer> map = new HashMap<>();
// 遍历数组中每个元素
for (int i = 0; i < nums.length; i++) {
// 获取每个元素于目标直接的差异值
int complement = target - nums[i];
// 判断该集合中是否有该差异值存在
if (map.containsKey(complement)) {
// 符合条件返回差异值的键值与当前的索引值(i)
return new int[] { map.get(complement), i };
}
// 无符合条件则将当前元素与索引值添加进集合中
map.put(nums[i], i);
}
// 给出参数异常提示
throw new IllegalArgumentException("No two sum solution");
}
}
提交结果:
两数之和(简单)-一遍哈希表.png
两次的提交结果可以看到暴力法比一遍哈希表内存消耗略低,而在执行用时却远远落后于一遍哈希表
小结:思维还是不够活跃,第一想法是用暴力法来破解,没有考虑到两两组合比较直接的耗时问题,以后动手前得多先规划好,再开码才行!
刚接触LeetCode不久,以上是本人根据自身了解解析,望大神们轻喷,多多帮助小弟快速提升.
有兴趣的小伙伴可以点下方链接一起来享受刷题的快(zhua)感(kuang)吧!
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
