算法题

[算法题] 两数之和

1. 两数之和

Link 难度:简单

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答:

1.暴力遍历法

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            int a=target-nums[i];
            for(int j=0;j<nums.length;j++){
                if(nums[j]==a&&i!=j)
                    return new int[] { i, j };
            }
        }
        return null;
    }
}

image-20200726203729541

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 a=target-nums[i];
            if(map.containsKey(a)&&map.get(a)!=i){
                return new int [] {map.get(a),i};
            }map.put(nums[i],i);
        }
        return null;
    }
}

image-20200726205552916

解题思路:

1.暴力法

查找用target减去每个数得到的结果是否在数组中()不为本身)

需要用到两层遍历

时间复杂度为O(n^2^) <==O(n)*O(n)

空间复杂度为O(1)

2.哈希表法

遍历数组nums,判断map中是否存在 target-nums[i] 的key值。

若不存在 将当前值 (nums[i]) 和下标 (i) 放入map中 map.put(nums[i],i)

若存在 将map中key对应的值 (map.get(a)) 和下标 (i) 返回 return new int [] {map.get(a),i};

时间复杂度为O(n) <== O(n)*O(1)

空间复杂度O(n)

知识点:

map.containsKey(a) 查找a是否在Hashmap map的中

containsKey
boolean containsKey(Object key)如果此映射包含指定键的映射关系,则返回 true。更确切地讲,当且仅当此映射包含针对满足 (key==null ? k==null : key.equals(k)) 的键 k 的映射关系时,返回 true。(最多只能有一个这样的映射关系)。

参数:
key – 测试是否存在于此映射中的键
返回:
如果此映射包含指定键的映射关系,则返回 true
抛出:
ClassCastException – 如果该键对于此映射是不合适的类型(可选)
NullPointerException – 如果指定键为 null 并且此映射不允许 null 键(可选)

时间复杂度为O(1)

Leave a Reply

邮箱地址不会被公开。 必填项已用*标注