哈希

Leetcode Hot100第一个小专题，三道题，分别是两数之和、字母异位词和最大连续子序列长度，暂时未记笔记.
今天是7月13号，决定重拾算法，先把之前的回忆一下，用java重构一下。

无重复字符的最长子串

力扣题目连接：两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]


只会存在一个有效答案

解题思路：

• 思路一：最简单的肯定是暴力了。两个for循环，不用动脑子，但是看这个专题，hash，就知道就有更迅速的方法。
• 思路二：hash，用一个map来存（值，下标），用i遍历数组，map中有没有target-nums[i]，如果用说明找到了，把找到的下标和当前下标返回，如果没有把当前（值，下标）放入map，继续遍历下一个。

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

字母异位词分组

力扣题目连接：字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

在 strs 中没有字符串可以通过重新排列来形成 "bat"。
字符串 "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 "ate" ，"eat" 和 "tea" 是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:

输入: strs = [""]

输出: [[""]]

示例 3:

输入: strs = ["a"]

输出: [["a"]]

解题思路：思路其实很简单，用一个Map<String,List<String>>来存储，键即为排序后的key，值就是该key中存储的原字符串列表，主要还是Java中一些方法不会灵活使用。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> result = new HashMap();
        for(String str:strs){
            char[] arr = str.toCharArray();
            Arrays.sort(arr);//String 是不可变的，没有排序方法，得先把字符串转化为字符数组。
            // String key = arr.toString();看起来语义很对，实际上toString是object的方法，返回的是首地址
            String key = new String(arr);
            List<String> list = result.getOrDefault(key,new ArrayList<String>());//之前没见过的方法，创建对象，从map中获取key对应的，如果没有创建一个默认的对象（第二个参数）
            list.add(str);
            result.put(key,list);

        }
        return new ArrayList<List<String>>(result.values());
    }
}

最长连续序列

力扣题目连接：最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
示例 3：

输入：nums = [1,0,1,2]
输出：3

解题思路：这种要去重的大多使用set比较方便，注意set是无序的，通过numSet.contains(currentNum+1)来判断是否有大一的序列元素；当我们遍历到某一个元素时，如果存在比其小一的元素，说明已经遍历过了，可以直接跳过。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for(int num:nums){
            numSet.add(num);
        }
        int result = 0;
        for(Integer num:numSet){
            if(!numSet.contains(num-1)){
                int currentNum = num;
                int currentLength = 1;
                while(numSet.contains(currentNum+1)){
                    currentNum++;
                    currentLength++;
                }
                result = Math.max(result,currentLength);
            }
            
        }
        return result;
    }
}
/*外层循环需要 O(n) 的时间复杂度，只有当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。根据上述分析可知，总时间复杂度为 O(n)，符合题目要求。 */

总结：哈希的这几个题目还是比较简单的，主要还是java中一些方法使用不够熟练。