Java实现LeetCode(1.两数之和)
作者:NullPointerExcept 时间:2021-06-03 02:11:19
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N)。
代码:
public static int[] twoSum1(int[] nums, int target) {
int[] label = new int[2];
for(int i=0;i<nums.length-1;i++) {
int tmp = target - nums[i];
for(int j=i+1;j<nums.length;j++) {
if(tmp == nums[j]) {
label[0] = i;
label[1] = j;
}
}
}
return label;
}
思路二:先排序,然后两个指针i,j,i从前开始,j从后开始查找,当nums[i]+nums[j]>target时,j--;当nums[i]+nums[j]<target时,i++;注意排序后,之前的下标数字已经变化了。时间复杂度O(N*Log2N)
代码:
public static int[] twoSum2(int[] nums, int target) {
int[] label = new int[2];
int[] tmpArr = new int[nums.length];
for(int i=0;i<nums.length;i++) {
tmpArr[i]=nums[i];
}
Arrays.sort(nums);
int i=0;
int j=nums.length-1;
while (i<j) {
if(nums[i]+nums[j]==target) {
label[0] = nums[i];
label[1] = nums[j];
break;
}else if(nums[i]+nums[j]>target){
j--;
}else {
i++;
}
}
for(int k=0;k<tmpArr.length;k++) {
if(tmpArr[k]==label[0]) {
label[0]=k;
}
if(tmpArr[k]==label[1]) {
label[1]=k;
}
}
return label;
}
思路三:利用空间换时间方式,用hashmap存储数组结构,key为值,value为下标。时间复杂度O(N)。
代码:
public static int[] twoSum3(int[] nums, int target) {
int[] label = new int[2];
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(int i=0;i<nums.length;i++) {
hashMap.put(nums[i], i);
}
for(int i=0;i<nums.length;i++) {
if(hashMap.containsKey(target-nums[i])&&hashMap.get(target-nums[i])!=i) {
label[0] = i;
label[1] = hashMap.get(target-nums[i]);
break;
}
}
return label;
}
github地址:https://github.com/xckNull/Algorithms-introduction
来源:https://blog.csdn.net/jek123456/article/details/79989145
标签:Java,LeetCode,两数之和
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Android编程之消息机制实例分析
2023-07-28 07:24:38
java开发微信分享接口的步骤
2021-08-22 12:30:59
![](https://img.aspxhome.com/file/2023/2/61652_0s.png)
值得收藏的2017年Java开发岗位面试题
2023-11-29 15:22:01
vue+springboot前后端分离工程跨域问题解决方案解析
2023-08-06 06:51:10
Java使用Lettuce客户端在Redis在主从复制模式下命令执行的操作
2023-11-28 21:38:19
![](https://img.aspxhome.com/file/2023/7/60797_0s.jpg)
Java设计模式的事件模型详解
2023-11-29 04:47:08
![](https://img.aspxhome.com/file/2023/2/59732_0s.png)
Java查找不重复无序数组中是否存在两个数字的和为某个值
2023-08-22 16:44:40
c语言动态数组示例
2023-11-02 22:56:44
Java之如何关闭流
2023-11-04 21:29:11
add方法理解ArrayList的扩容机制
2023-11-24 02:16:28
java模拟TCP通信实现客户端上传文件到服务器端
2023-11-26 10:14:49
Java中SimpleDateFormat日期格式转换详解及代码示例
2023-09-04 22:13:43
![](https://img.aspxhome.com/file/2023/1/58461_0s.png)
Java利用移位运算将int型分解成四个byte型的方法
2023-11-09 08:25:00
![](https://img.aspxhome.com/file/2023/4/59334_0s.png)
Java 网络编程总结
2023-11-10 22:19:29
![](https://img.aspxhome.com/file/2023/1/59071_0s.png)
详解SpringBoot统一响应体解决方案
2023-03-08 08:54:13
通过FeignClient调用微服务提供的分页对象IPage报错的解决
2022-01-27 20:19:23
![](https://img.aspxhome.com/file/2023/7/63057_0s.png)
Java+Nginx实现POP、IMAP、SMTP邮箱代理服务
2023-11-26 10:31:47
![](https://img.aspxhome.com/file/2023/7/59327_0s.jpg)
Java实现的计算最大下标距离算法示例
2022-02-09 19:14:37
Java String类字符串的理解与认知
2022-05-10 17:27:12
![](https://img.aspxhome.com/file/2023/5/60825_0s.png)
java 读取本地文件实例详解
2023-08-12 20:41:32