LeetCode笔记:1. Two Sum
2023-03-15 23:20:29 时间
问题:
Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
大意:
给出一个整型数组,返回其中两个可以相加得出目的数字的数字的位置。 你可以假设所有输入都有一个解决方案。 例子: 给出 nums = [2, 7, 11, 15], target = 9, 因为 nums[0] + nums[1] = 2 + 7 = 9, 返回 [0, 1]。
思路:
一开始我的做法是用一个长度为目的数字的数组来记录给出的数组中所有小于目的数的数字所在的位置,然后遍历这个数组来看有没有能相加等于目的数的,最后取出其位置。但是当发现给出的数组中可能有负数时,这个做法就崩了。
重新分析一下要求,其实我们有两个需求,一是记录出现过的数字,由于可能有负数,因此已经无法缩小要记录的数字的范围了,二是要记录数字所在的位置,不能做个排序然后位置就不知道了。基于这两个要求,其实HashMap很符合我们的需要。
我们用一个HashMap来记录遍历过程中每次出现的数字及其位置,数值是key,位置是值,同时判断之前有没有记录过正好与当前数字相加等于目的数的数字,有就取出这两个数字的位置,如果遍历完了还没有那就是没有了。
代码(Java):
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[0] = map.get(target - nums[i]);
result[1] = i;
return result;
}
map.put(nums[i], i);
}
return result;
}
}
相关文章
- 金融服务领域的大数据:即时分析
- 影响大数据、机器学习和人工智能未来发展的8个因素
- 从0开始构建一个属于你自己的PHP框架
- 如何将Hadoop集成到工作流程中?这6个优秀实践必看
- SEO公司使用大数据优化其模型的5种方法
- 关于Web Workers你需要了解的七件事
- 深入理解HTTPS原理、过程与实践
- 增强分析:数据和分析的未来
- PHP协程实现过程详解
- AI专家:大数据知识图谱——实战经验总结
- 关于PHP的错误机制总结
- 利用数据分析量化协同过滤算法的两大常见难题
- 怎么做大数据工作流调度系统?大厂架构师一语点破!
- 2019大数据处理必备的十大工具,从Linux到架构师必修
- OpenCV中的KMeans算法介绍与应用
- 教大家如果搭建一套phpstorm+wamp+xdebug调试PHP的环境
- CentOS下三种PHP拓展安装方法
- Go语言HTTP Server源码分析
- Go语言HTTP Server源码分析
- 2017年4月编程语言排行榜:Hack首次进入前五十