小编给大家分享一下Java实现LeetCode的方法,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 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;}
以上是“Java实现LeetCode的方法”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注编程网行业资讯频道!