leetcode-算法系列-两数之和
2024-10-21 15:49:09
本系列的题目都是出自于"leetcode" 用博客记录是为了加强自己的记忆与理解,也希望能和大家交流更好更优的解题思路.
题目:
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1] 解决方案1( java ):
思路: 数组中某个元素的值为 c + x(未知数) = target,x = target-c, 那么依次遍历所有元素,设元素为c,求出x后检查x是否在数组中,如果存在就返回元素索引。
暴力法:
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[j]=target-nums[i] ){ return new int[]{i,j} }
}
} 效率: 数组中有x个元素,最坏情况需要遍历所有元素x*x次,那么时间复杂度为 O (n^2 ) ; 由于没有使用任何临时变量,所以复杂度为 O(1);
优化方案1:
利用哈希。哈希表中存储数组中每个元素的值和坐标 ,可以通过值查询坐标 而不用遍历所有数组.
一遍哈希:
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++ ){
int key= target-nums[i];
if(map.containsKey(key)){ return new int[]{map.get(key),i } }
map.put(nums[i],i);
}
时间复杂度: 每个元素的对应解的查找只有一次,所以为 O(n),
空间复杂度: O(n) 需要额外空间来来存储数组的每个元素. 注意: 以上大部门内容转载于 leetcode,请注意~!!!
最新文章
- java实现的类和表持久化
- 给RecyclerView实现的GridView加上HeaderView和FooterView
- 对整站的a链接进行监控,对匹配规则进行指定页面的跳转
- IOS GCD 使用 (二)
- oracle暂时表空间 ORA-01652:无法通过16(在表空间XXX中)扩展 temp 字段
- codevs 2612 最有分解方案 (贪心)
- C++标准库之 Lower_Bound, upper_Bound
- UVA - 12119 The Bells are Ringing (枚举)
- CFormView动态调整对话框的尺寸和调整比例控制的部署
- EF4.1: Add/Attach and Entity States(EF中的实体状态转换说明)
- 安装MySQL提示“请键入 NET HELPMSG 3534 以获得更多的帮助”的解决办法
- 安装oracle11g不能启动图形化界面
- 记录一份Oracle 正确的监听配置文件listener.ora与tnsnames.ora
- ant design + react,自动获取上传音频的时长(react-audio-player)
- sql server 小技巧(5) Sql server 获取指定字符后的所有字符 - 去掉指定字符前的所有字符
- HDU 1166 - 敌兵布阵 - [线段树][树状数组]
- 并发编程(三)Promise, Future 和 Callback
- Sprint 3.0
- ViewStub用法
- jsp+servlet+jdbc实现对数据库的增删改查