两数之和

常规方法，遍历两次，复杂度是0n²的，无法接受。用哈希表， Map<Integer, Integer> hash = new HashMap<>()，HashMap可以做到O(1)复杂度查数字。

// 常规方法 遍历两次
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < nums.length; j++){
                if(i == j) continue;
                if(nums[i] + nums[j] == target){
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}

注意，先检查后存入​​：确保不会匹配到自己。

// 哈希表解法
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int needed = target - nums[i];
            if(hash.get(needed) != null && hash.get(needed) != i){
                return new int[]{hash.get(needed), i};
            }
            hash.put(nums[i], i);  // 先检查 再放入hash 确保不会匹配到自己
        }
        return new int[0];
    }
}

字母异位词分组

用字符串排序+哈希，字符串排序要转换成字符数组。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new ArrayList<>();
        HashMap<String, List<String>> hash = new HashMap<>();  // key为sort后的字符串 value为异位词的list
        // 直观思路 字符串排序对比
        for(int i = 0; i < strs.length; ++i){
            String temp = strs[i];
            char[] s = temp.toCharArray();
            Arrays.sort(s); // 转化成char才能sort
            String stemp = new String(s); // 转化回String

            if(hash.containsKey(stemp) == false){ // 为空 创建
                List<String> keyString = new ArrayList<>();
                keyString.add(temp);
                hash.put(stemp, keyString);
            }else{
                List<String> keyString = hash.get(stemp);
                keyString.add(temp);
                hash.put(stemp, keyString);
            }
        }
        // 最后把hash中所有的元素取出来放到list里
        for(List<String> value : hash.values()){
            list.add(value);
        }
        return list;
    }
}

最长连续序列

用HashSet，所有的数装入set，然后一个个遍历，如果当前数n，set中存在n-1就continue，否则就循环判断是否存在n+1，n+2…

版本1，超时，10个用例没过：

//  版本1 有10个用例超时 最坏情况下会On²
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        HashSet<Integer> set = new HashSet<>();
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }
        for(int i = 0; i < nums.length; i++){
            int cnt = 1;
            int temp = nums[i];
            while(set.contains(temp + 1)){
                cnt++;
                temp++;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }
}

上述代码对每个数字都尝试向后查找连续序列，有很多重复查找。需要剪掉一些无用的计算，加一句if (!set.contains(num - 1)) ，保证序列从最小值开始技术。

版本2， 还是有4个用例没过，需要再优化。

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        HashSet<Integer> set = new HashSet<>();
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }
        for(int i = 0; i < nums.length; i++){
            int cnt = 1;
            int temp = nums[i];
            if(!set.contains(temp - 1)){
                while(set.contains(temp + 1)){
                    cnt++;
                    temp++;
                }
                res = Math.max(res, cnt);
            }
        }
        return res;
    }
}

版本3，不遍历nums数组而是遍历哈希集合（已去重），这样可以避免重复元素遍历！

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        HashSet<Integer> set = new HashSet<>();
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            set.add(nums[i]);
        }
        for(int v : set){ //遍历哈希集合而非数组！
            if(set.contains(v - 1)){
                continue;
            }
            int temp = v;
            int cnt = 1;
            while(set.contains(temp + 1)){
                cnt++;
                temp++;
            }
            res = Math.max(cnt, res);
        }
        return res;
    }
}