题解 | #两数之和#
两数之和
https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f
我的第一种方法,虽然通过两个for循环,能够得出答案,但是,复杂度是O(n^2)太高了,所以不通过,
第二种方法,则是巧妙了利用了hashmap的特性,加快了整个判断的速度:
(target - nums[i]) = key,而通过判断map.contains(key),就能知道两个和等于target的值了
key是第一个值,nums[i]是第二个值,而第一个值的下标在,key对应的value里面。
也就是
1,通过保存的的map的key,来求得 key = target - nums[i],也即是,key + nums[i] = target;
2,而key又能够,保存相应的index坐标值,所以,通过一个数据hashmap的key,value,同时保存了两个值。
3,最终简化了,整个比对的复杂度。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组 */ // public int[] twoSum (int[] numbers, int target) { // if(numbers==null || numbers.length==0) { // return null; // } // for(int i=0; i<numbers.length; i++) { // for(int j=i+1; j<numbers.length; j++) { // if(numbers[i]+numbers[j] == target) { // return new int[] {i+1, j+1}; // } // } // } // return null; // } public int[] twoSum (int[] numbers, int target) { int[] res = {-1, -1}; int n = numbers.length; Map<Integer,Integer> map = new HashMap<>(); for(int i=0; i<numbers.length; i++) { if(map.containsKey(target-numbers[i])) { return new int[]{map.get(target-numbers[i])+1, i+1}; } else { map.put(numbers[i], i); } } return res; } }