[Java/LeetCode]算法练习:两数之和(1/simple)
2023-09-27 14:24:42 时间
1 题目
2 思路与代码
2.1 思路一:暴力法(两层For循环)
- 思路一:暴力法(两层For循环)
- 时间复杂度:O(n^2)
- 对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,这将耗费 O(n) 的时间。因此时间复杂度为 O(n^2)。
- 空间复杂度:O(1)
- 原理:遍历每个元素 xx,并查找是否存在一个值与 target - x相等的目标元素
- 时间复杂度:O(n^2)
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target){
static int result[2]= {0};
for(int i=0;i<numsSize;i=i++){
for(int j=i+1;j<numsSize;j=j++){ //【trick】“int j=i+1;”而非“int j=0”
if(nums[i]+nums[j]==target){
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
2.2 思路二:两遍哈希表
- 思路二:两遍哈希表
- 时间复杂度:O(n)
- 把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ,所以时间复杂度为O(n)
- 空间复杂度:O(n)
- 所需的额外空间取决于哈希表中存储的元素数量,该表中存储了 n 个元素
- 时间复杂度:O(n)
class Solution {
/*
思路:两遍哈希表
推荐文献:
https://baijiahao.baidu.com/s?id=1628609734622761569&wfr=spider&for=pc
*/
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int j=0;j<nums.length;j++){
int tmp = target - nums[j];
if(map.containsKey(tmp) && map.get(tmp)!=j){
return new int [] { j, map.get(tmp) };
}
}
throw new IllegalArgumentException("No two sum solution!");
}
}
2.3 思路三:一遍哈希表
- 思路三:一遍哈希表
- 时间复杂度:O(n)
- 只遍历了包含有n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间
- 空间复杂度:O(n)
- 所需的额外空间取决于哈希表中存储的元素数量,该表最多需要存储 n 个元素。
- 原理:通过思路二,可以推得:上述过程可以一次完成。在进行迭代并将元素插入到表中的同时,我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在,那我们已经找到了对应解,并立即将其返回。
- 时间复杂度:O(n)
class Solution {//一次Hash查表
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap();
for(int i=0;i<nums.length;i++){
int tmp = target - nums[i];
if(map.containsKey(tmp) && map.get(tmp)!=i){
return new int [] { i, map.get(tmp) };
} else {
map.put(nums[i],i);
}
}
// for(int j=0;j<nums.length;j++){
// int tmp = target - nums[j];
// if(map.containsKey(tmp) && map.get(tmp)!=j){
// return new int [] { j, map.get(tmp) };
// }
// }
throw new IllegalArgumentException("No two sum solution!");
}
}
3 参考文献
4 博文遗留问题
- (数据结构/Java中)HashMap/哈希表 查询的原理与实现?
相关文章
- Java语法糖之泛型与类型擦除
- JAVA线程同步 (二)notify()与notifyAll()-***
- Java中的static关键字解析
- [LeetCode][Java] Minimum Depth of Binary Tree
- 【LeetCode刷题Java版】Reverse Words in a String
- [Java/LeetCode]算法练习:转变日期格式(1507/simple)
- Java中C/S通讯程序设计一例
- 115个Java面试题和答案——终极列表(下)
- 【LeetCode-面试算法经典-Java实现】【054-Spiral Matrix(螺旋矩阵)】
- 在写junit test 的时候出现的java.lang.UnsupportedClassVersionError问题
- Java 取得文件名的后缀
- 大数据必学Java基础(一百一十三):监听器概念引入
- 大数据必学Java基础(三十五):深入了解关键词this
- LeetCode-171. Excel 表列序号(java)
- LeetCode-190. 颠倒二进制位(java)
- LeetCode-168. Excel表列名称(java)
- LeetCode-111. 二叉树的最小深度(java)
- LeetCode-101. 对称二叉树(java)
- LeetCode-100. 相同的树(java)
- LeetCode-66. 加一(java)
- LeetCode-14. 最长公共前缀(java)
- LeetCode-13. 罗马数字转整数(java)
- LeetCode-9. 回文数(java)
- LeetCode-861. 翻转矩阵后的得分(Java实现)
- LeetCode:94. 二叉树的中序遍历(java)