题解 | #两数之和#

两数之和

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;
    }
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务