哈希表算法面试题解析

有效的字母异位词

• 其实就是两个单词，比较是不是字母相同，只是位置错乱

  
  image.png

• 那么如上图，有两种方法
  第一种方法是遍历两个单词的每一个字母，并按照26个英文字母的顺序进行排序，排序完毕，比较是否相同即可。这种方法的时间复杂度是O(N * log N)
  第二种方法是记录每个单词中字母出现的次数，用map统计。最后比较map中key 和 value是否完全相同并一一对应。这种方法的时间复杂度是O(N)。
  那么明显使用Map处理此问题要优于排序。

class Solution {
    public boolean isAnagram(String s, String t) {
        // 初始化Map 用来存储字符出现的次数
        Map<Character, Integer> map = new HashMap<>();
        // 遍历第一个字符串每一个字母添加到字典里每次value+1
        for (char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch,0) + 1);
        }
        // 遍历第二个字符串每一个字母 没遍历一次 从map中删除一次次数 如果为0 则移除键值对
        for (char ch : s.toCharArray()) {
            Integer count = map.get(ch);
            if (count == null) {
                return false;
            } else if (count > 1) {
                map.put(ch, count - 1);
            } else {
                map.remove(ch);
            }
        }
        // 如果map为空 则证明一一对应 也就是单词的每个字母出现的次数相同 也就是两个单词是有效的字母异位词。
        return map.isEmpty();
    }
}

两数之和

image.png

https://leetcode-cn.com/problems/two-sum/

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 判断是否满足条件
        if (nums.length < 1) {
            throw new IllegalArgumentException();
        }
        // 初始化一个map key为数组中每个元素值与目标值差值，value为每个元素的下标
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            // 如果map中的key不包含该元素的值 则把该元素与目标值的差值当作key加入到map中 
            if (!map.containsKey(nums[i])) {
                map.put(target - nums[i], i);
            } else {
                // 包含了 则说明map中存在key于新元素相加等于目标值 则返回元素下标数组即可
                return new int[]{i, map.get(nums[i])};
            }
        }
        throw new IllegalArgumentException();
    }
}

三数之和

image.png

https://leetcode-cn.com/problems/3sum/

从上图可以看出此题，解法有三种，第一种暴力解法不再解释了，时间复杂度太高。肯定超时。第二种解法，使用的是用空间换时间。时间复杂度是O(N平方)。第三种解法使用的是先排序，后两边夹求和的方式。时间复杂度也是O(N平方)，但是没有开辟新的空间。所以第三种解法是最优的。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 初始化结果数组
        List<List<Integer>> res = new ArrayList<>();
        // 首先对Array进行排序 从小到大
        Arrays.sort(nums);
        // 第一层遍历 拿到a与目标值0的差值opppsite
        for (int i = 0; i < nums.length; i++) {
            int opposite = -nums[i];
            // 判断nums满足条件之后 声明i之后 左右两个index 用来两边移动取值
            if (i == 0 || nums[i] != nums[i - 1]) {
                int left = i + 1;
                int right = nums.length - 1;
                
                // 判断左边是否小于右边 以防止都走到中间
                while(left < right) {
                    // 得到左右之和
                    int twoSum = nums[left] + nums[right];
                    // 判断左右之和和oppisite是否相等 如果相等 则满足条件 将结果加入结果数组
                    if (twoSum == opposite) {
                        // 初始化一组结果数组 并加入总的结果数组
                        List<Integer> ans = new ArrayList<>();
                        ans.add(nums[i]);
                        ans.add(nums[left]);
                        ans.add(nums[right]);
                        res.add(ans);
                        // 左右index同时移动
                        left = moveLeft(nums, left, right);
                        right = moveRight(nums, left, right);
                        
                        // 两和小于差值  则左边继续忘后移会使得两和更大 得到结果更快 
                    } else if (twoSum < opposite) {
                        left = moveLeft(nums, left, right);
                    } else {
                        // 反之 则右边向左移动 会使得得到结果更快
                        right = moveRight(nums, left, right);
                    }
                }
            }
        }
        return res;
    }
    
    // left index向右移动的方法
    private int moveLeft(int[] nums, int left, int right) {
        // 获取left向右移动一位的值 这里left往后已经移动一位了
        int num = nums[left++];
        // 首要条件判断left是否小于right
        while (left <= right) {
            // 判断左边下一位值是否和左边的值相等 不等则直接跳出循环
            if (nums[left] != num) break;
            // 如果相等了就再往后移动一位 直到不相等为止
            left++;
        }
        return left;
    }
    
    // right index向左移动的方法
    private int moveRight(int[] nums, int left, int right) {
        // 获取right向左移动一位的值
        int num = nums[right--];
        while (left <= right) {
            if (nums[right] != num) break;
            right--;
        }
        return right;
    }
}