《LeetCode热题100》---＜哈希三道＞

第一道：两数之和（简单）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        Arrays.sort(nums);
        while (left < right){
            if(nums[left] + nums[right] < target) {
                left++;
            }else if(nums[left] + nums[right] > target){
                right--;
            }else {
                return new int[]{left,right};
            }
        }
        return new int[]{left,right};
    }
}

方法一：暴力枚举

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

方法二：哈希表

注：

java的官方文档建议我们在初始化哈希表的时候尽量写入哈希表的容量，避免哈希表扩容所带来的性能消耗。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        Map<Integer, Integer> hashTable = new HashMap<Integer, Integer>(len-1);
        hashTable.put(nums[0],0);//向哈希表存入数组第一个数
        //从第二个数开始遍历数组，看哈希表中是否存在target减去此时数组的数所对应的值
        //如果有，则返回下标。
        //没有则将这个数放进哈希表。并存入数组下标。
        for (int i = 1; i < len; ++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];
    }
}

---

 第二道：字母异位词分组（中等）

方法一：哈希+排序 

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

方法二：哈希+计数

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

第三道：最长连续序列（中等）

暴力的方法是 O(n) 遍历数组去看是否存在这个数，我们就不多说了，这里我们来看更高效的哈希表法。

哈希表

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }

        int longestStreak = 0;

        for (int num : set) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

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

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}