给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
思路一：最直接的思维，两次遍历查询，时间复杂度O(N*N)。
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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)
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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)。
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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
到此这篇关于Java实现LeetCode（两数之和）的文章就介绍到这了,更多相关Java实现两数之和内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/jek123456/article/details/79989145
