1.两数之和

 什么时候使用哈希法？
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

为什么用map
使用map：key：元素；value：下标

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

//1.两数之和
class Solution {
    //1.暴力for循环
    public int[] twoSum1(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                for (int j = i+1; j < nums.length; j++) {
                    if (nums[i]+nums[j]==target)
                        return new int[]{i,j};
                }
            }
            return null;
    }


    //2.哈希表
    /*
    为什么使用哈希表？
    ：要判断这个元素是否出现过/在这个集合
    遍历到n，则需要判断target-n是否出现过
    为什么用map
    使用map：key：元素；value：下标
     */
    public int[] twoSum2(int[] nums, int target) {
        Map map = new HashMap<Integer,Integer>();
        for (int i = 0; i < nums.length; i++) {
            int k = target- nums[i];
            if (map.containsKey(k))
                return new int[]{i, (int) map.get(k)};
            else
                map.put(nums[i],i);
        }
        return null;
    }
}

public class TwoSum_1 {
    public static void main(String[] args) {
        int[] arr=new int[]{3,2,4};
        int target=6;
        Solution solution=new Solution();

        //1
        System.out.println("@1:\n"+ Arrays.toString(solution.twoSum1(arr,target)));
        //2
        System.out.println("@1:\n"+ Arrays.toString(solution.twoSum2(arr,target)));

    }
}

49.字母异位词分组

49. 字母异位词分组 – 力扣（LeetCode）

要把字母异位词分组，就得找到一种方法来判定哪些字符串是字母异位词。由于字母异位词是由相同字母组成的，所以对它们的字母进行排序后，得到的字符串是一样的。例如，“eat”、“tea” 和 “ate” 排序后都变成了 “aet”。基于这个特性，就可以使用排序后的字符串作为标识，将具有相同标识的字符串归为一组。

import java.util.*;

//49.单词异位词分组
public class GroupAnagrams_49 {
    static class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            //空串特殊处理
            if (strs.length == 0) return new ArrayList<>();
            //构造散列表，key为对字符串转化为字符数组排序后的唯一字符串序列，value为唯一对应的list结果
            Map<String,List<String>> map=new HashMap<>();
            for (String s:strs){
                char[] chars = s.toCharArray();
                //异位词排序后序列相同
                Arrays.sort(chars);
                //排序后的结果构造为字符串便于比较,作为key
                String key=String.valueOf(chars);

                if (map.containsKey(key)){
                    map.get(key).add(s);
                }else {
                    List<String> newList = new ArrayList<>();
                    newList.add(s);
                    map.put(key, newList);
                }
            }
            return  new ArrayList<>(map.values());
        }
    }

    public static void main(String[] args) {
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        Solution solution = new Solution();
        List<List<String>> result = solution.groupAnagrams(strs);
        for (List<String> group : result) {
            System.out.println(group);
        }
    }
}

注：语法问题：指定map泛型String,List<String>时要指定在Map位置，而非后面的Hashmap；

128.最长连续序列

128. 最长连续序列 – 力扣（LeetCode）

1. 去重处理：将数组中的所有元素存入哈希表中，自动完成去重。
2. 寻找序列起点：遍历哈希表中的每个元素，判断其是否为一个连续序列的起点。判断方法是检查该元素减 1 是否存在于哈希表中。
3. 扩展序列：如果当前元素是序列起点，则尝试向右扩展该序列，统计其长度。
4. 记录最长长度：在扩展过程中，记录找到的最长连续序列长度。

为什么用哈希？

用于快速查找num-1存不存在！

class Solution {
    public int longestConsecutive(int[] nums) {
        // 将数组转换为集合以删除重复元素
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int ans = 0;

        for (int num : numSet) {
            // 只有当num是序列的起始元素时才开始计数
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLen = 1;

                // 向右扩展计数
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentLen++;
                }

                ans = Math.max(ans, currentLen);
            }
        }

        return ans;
    }
}