内容简介:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。示例:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
第一次看到这个题目的解法
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,List<Integer>> map = new HashMap<>(); for(int i=0;i<nums.length;i++){ //第一个元素 for(int j=nums.length-1;j>0;j--){ //访问后面的元素 int key = nums[i] + nums[j]; List<Integer> value = new ArrayList<>(); value.add(i); value.add(j); map.put(key,value); } } List<Integer> list = map.get(target); Integer[] arr = new Integer[list.size()]; //Integer不能直接转换int数组 list.toArray(arr); // Integer集合转int数组 int[] result = new int[arr.length]; for (int i = 0; i < arr.length; i++) { result[i] = arr[i]; } return result; } } 复制代码
虽然只是简单的一个小题目,但是解法做的也有点太麻烦了 就优化了一下
class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; int m = 0; int n = 0; for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { m = i; n = j; break; } else { continue; } } } result[0] = m; result[1] = n; return result; } } 复制代码
没有使用 java 的 工具 类
上面的解法都需要遍历两次,时间复杂度都是O(n^2)
看了一下官网给出的答案,只需要遍历一次就可以获取结果。
class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i++){ int comple = target - nums[i]; if(map.containsKey(comple)){ return new int[] {map.get(comple),i}; } map.put(nums[i],i); } throw new IllegalArgumentException("No two sum solution"); } } 复制代码
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
About Face 3
Alan Cooper、Robert Reimann、David Cronin / John Wiley & Sons / 2007-5-15 / GBP 28.99
* The return of the authoritative bestseller includes all new content relevant to the popularization of how About Face maintains its relevance to new Web technologies such as AJAX and mobile platforms......一起来看看 《About Face 3》 这本书的介绍吧!