Hot100之哈希

1两数之和

题目

思路解析

解法1--两次循环

解法2--哈希表一次循环

代码

解法1--两次循环

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int nums1[] = new int[2];
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (nums[i] + nums[j] == target) {
                    nums1[0] = i;
                    nums1[1] = j;
                    return nums1;
                }
            }
        }
        return nums1;
    }
}

解法2--哈希表一次循环

import java.util.HashMap;
import java.util.Map;

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

49字母异位词分组 

题目

思路解析

我们利用一个Map结构Map<String,List>

然后我们把字符串String变成我们的char【】数组，然后Arrays.sort（）对字符数组进行排序

将排序后的字符数组变成String放到Map中（这样子就能保证ate，eat，tea的value就是排序后的字符数组aet）

最后通过return new ArrayList(map.values())，将Map中的所有键值对构造成List

代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0 || strs == null) {
            return new ArrayList();
        }

        Map<String, List> map = new HashMap<String, List>();

        for (String s : strs) {
            // 将字符串转化为字符数组
            char[] chars = s.toCharArray();

            // 对字符数组按照字母顺序排序
            Arrays.sort(chars);

            // 将排序后的字符串作为哈希表中的key值
            String key = String.valueOf(chars);

            // 判断哈希表中是否有该key值
            if (!map.containsKey(key)) {
                // 若不存在，则为新的异位词语，在map中创建新的键值对
                map.put(key, new ArrayList());
            }

            // 将该字符串放在对应key的list中
            map.get(key).add(s);
        }

        // 返回map中所有键值对象构成的list
        return new ArrayList(map.values());
    }
}

128最长连续数列

题目

思路解析

我们通过Set结构的contains()来看看是否有连续的变量

我们开始计算的条件是：我们该元素-1不存在，说明这就是连续递增元素的头，我们从这个开始计算

如果我们前面元素存在，说明这个元素不是连续递增元素的头，我们要求最长连续数列，所以没必要计算

        for (int num : set) {
        
            // 说明不会重复,因为1,2,3,4我们已经算完了,我们还从2,3,4算起就没必要了
            // 因为我的最长已经从第一个最小数字开始算出来了
            //所以我们在元素x的时候，如果我们的元素x-1不存在，说明前面没有连续的，我们在x开始遍历
            //如果我们的元素x-1存在，说明它不是连续递增的头，所以没必要遍历
            if (!set.contains(num - 1)) {
                int currentNum = num; // 一个变量用来++
                int currentMax = 1;

                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentMax++;
                }

                maxlength = Math.max(maxlength, currentMax);
            }
        }

代码

class Solution {
    public int longestConsecutive(int[] nums) {
        // 利用Set结构,把数字都放到Set结构里面
        Set<Integer> set = new HashSet<Integer>();

        for (int num : nums) {
            set.add(num);
        }

        int maxlength = 0;

        for (int num : set) {
        
            // 说明不会重复,因为1,2,3,4我们已经算完了,我们还从2,3,4算起就没必要了
            // 因为我的最长已经从第一个最小数字开始算出来了
            //所以我们在元素x的时候，如果我们的元素x-1不存在，说明前面没有连续的，我们在x开始遍历
            //如果我们的元素x-1存在，说明它不是连续递增的头，所以没必要遍历
            if (!set.contains(num - 1)) {
                int currentNum = num; // 一个变量用来++
                int currentMax = 1;

                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentMax++;
                }

                maxlength = Math.max(maxlength, currentMax);
            }
        }

        return maxlength;
    }
}