运用哈希表求解问题

哈希表是根据键（key）而直接访问在内存存储位置的数据结构，也就是说，它通过计算一个关于键值的函数，将所需查询的数据 映射 到表中一个位置来访问记录，这加快了查找速度。

题一：力扣1.两数之和

创建一个哈希表，对于每一个X哈希表中是有否target-x，我首先的想法是把所有数据存入表中在进行查找，可是这样就要进行两次循环，时间和内存都有一定量的浪费

class Solution {
    public int[] twoSum(int[] nums, int target) {
         HashMap hashMap = new HashMap<>();
        for(int i=0;i< nums.length;i++){
            hashMap.put(nums[i],i);
        }
        for(int i=0;i< nums.length;i++){
            if(hashMap.containsKey(target-nums[i])){
                int a=hashMap.get(target-nums[i]);
                if(a!=i){
                return new int[]{a,i };
                }
            }
        }
     return new int[0];   

    }
}

下面是力扣的官方题解

在一次循环中完成两个任务，如果添加的数字已经有满足的就不用再添加了，之所以后添加而不添先加是为了避免自身加自身等于目标值的情况

class Solution {
    public int[] twoSum(int[] nums, int target) {
       Map hashtable = new HashMap();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
     }
}

题二，力扣167两数之和 II - 输入有序数组

与上述解法基本一致，但其实这个方法并没有利用这个题的有序性，时间和内存消耗比较严重

其他更优解在写二分和双指针时会补充上

class Solution {
    public int[] twoSum(int[] numbers, int target) {

       Map hashtable = new HashMap();
        for (int i = 0; i < numbers.length; ++i) {
            if (hashtable.containsKey(target - numbers[i])) {
                return new int[]{hashtable.get(target - numbers[i])+1, i+1};
            }
            hashtable.put(numbers[i], i);
        }
        return new int[0];
     }
}

 题三，找到所有数字中消失的数字(原地修改）

用一个哈希表记录数组中的数字，用一个长度为n+1的新数组代替哈希表，将旧数组中的数字作为新数组的数字下标，之后遍历新数组数值为零的元素的数字下标即为消失的数字

class Solution {
    public List findDisappearedNumbers(int[] nums) {
  int n = nums.length;
        int[] hash = new int[n + 1];
        for (int i = 0; i < n; i++){
            hash[nums[i]]++;
        }
        List list=new ArrayList();
        for (int i = 0; i < n+1; i++) {
            if (hash[i]==0&&i!=0) {
                list.add(i);
            }
        }
        return list;
    }
}