LeetCode-1:从数组中找到和为指定值得两个元素


题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

思路:暴力法两层遍历可以在 O(n2) 的复杂度下实现,但这显然不是我们想要的答案,肯定有复杂度更优的解法。例如 O(nlogn) 的解法,甚至 O(n) 的解法。

O(nlogn) 我们首先想到快排还有二分查找,确实这样可以实现,首先使用快排对数组排序,然后两层循环嵌套但内侧循环使用二分查找,此时时间复杂度就是 O(nlogn),实现代码略微有些繁琐

O(n) 有没有可能呢?在这个题目里遍历一次是不可能省掉的,也就是说必须在遍历的过程中有一个 O(1) 复杂度的方法去查找另一个元素,O(1) 复杂度立马联想到 hash,hash 常用的结构就是 HashSet 和 HashMap,这里因为要返回下标,因此使用 HashMap,其 key 为数组中的值,value 为其下标,实现如下。

注意边界条件,另外数组中允许有重复的元素,下面算法都可以实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums==null || nums.length<2)
            return null;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            int other = target - nums[i];
            if(map.containsKey(other)){
                return new int[]{map.get(other), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}
Copyright © jverson.com 2019 all right reserved,powered by Gitbook 22:14:05

results matching ""

    No results matching ""