leetcode算法-哈希表总结

系列文章目录

---

---

前言

关于哈希的基础知识的学习 请点开！！！！
哈希有拉链法和开放寻址法
这俩方法有模板
还有字符串哈希
模板都是用的数组 简便快捷了一点

对于数之和的那种 同一个数组就用双指针 不同数组 还是哈希法比较好 哈希加上动态数组那种
Set和arrayList转换成数组
a.stream().mapToInt(x->x).toArray();

一、 242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

class Solution {
    public boolean isAnagram(String s, String t) {
       int[] r = new int[26] ;
       for(char c : s.toCharArray()) r[c-'a']++ ;
       for(char c : t.toCharArray()) r[c-'a']-- ;
        for(int i : r) if(i != 0 ) return false;
        return true;
 
    }
}

 int[] record = new int[26];

        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a']--;
        }
        
        for (int count: record) {
            if (count != 0) {
                return false;
            }
        }
        return true;

     class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> maps = new HashMap<Character, Integer>();
        Map<Character, Integer> mapt = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i ++ ){
            char c = s.charAt(i);
            maps.put(c, maps.getOrDefault​(c, 0) + 1);
        }
        for (int i = 0; i < t.length(); i ++ ){
            char c = t.charAt(i);
            mapt.put(c, mapt.getOrDefault​(c, 0) + 1);
        }
        return maps.equals(mapt);

 
    }
}

 

变形1 383.赎金信

class Solution {
    public boolean canConstruct(String s, String t) {
            int[] r = new int[26];
            for(char c: t.toCharArray()) r[c-'a']++;         
            for(char k : s.toCharArray()){
                r[k-'a']--;
                if( r[k-'a'] <  0)return false;
            }
                return true ;
            
    }
}

49.字母异位词分组

438.找到字符串中所有字母异位词

双指针算法 滑动窗口

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

 

利用模板的话

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        //此map为pMap
        Map<Character, Integer> map = new HashMap<>();
        for (char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int needToMatch = map.size();
        int r = 0, l = 0;

        while(r < s.length()) {
            if (map.containsKey(s.charAt(r))) {
                map.put(s.charAt(r), map.get(s.charAt(r)) - 1);
                //count 1--> 0
                if (map.get(s.charAt(r)) == 0) {
                    needToMatch--;
                }
            }
            //when length exceeds
            while (r - l + 1 > p.length()) {
                if (map.containsKey(s.charAt(l))) {
                    if (map.get(s.charAt(l)) == 0)  needToMatch++;
                    map.put(s.charAt(l), map.get(s.charAt(l)) + 1);
                }
                l++;
            }
            //以上操作恢复到p.length() 长度
            //如果此时 needToMatch正好为0，也就意味着 没有再需要匹配的字符了(并且匹配过的字符都已经count相等)
            //那么这一段 就是个anagram
            if (needToMatch == 0) {
                res.add(l);
            }
            r++;
        }
        return res;
    }
}

 

双指针算法是包含滑动窗口算法的 所以要是滑动窗口的话 还是指的是双指针算法

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] hash = new int[26];
        for(char c : p.toCharArray()) hash[c-'a']++;
        int t = 0 ;
        for(int i = 0 ; i < 26 ; i++){
              if(hash[i] != 0 )  t++;
        }
        List<Integer> res = new ArrayList<>();
         char[] a = s.toCharArray();
         //i和j为窗口 kind 为种类
        for(int i = 0 , j = 0 ,kind = 0; i < s.length() ; i++ ){
            if(--hash[a[i]-'a'] == 0) kind++;
            while(i - j + 1 > p.length()){//收缩窗口
            //if==0说明删之前a[j]满足要求
                if(hash[a[j]-'a'] == 0) kind--;
                hash[a[j++]-'a']++;
            }
            if(kind == t ) res.add(j);
        }
        return res ;
    }
}

二、 349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

//将结果集合转为数组-法一
return resSet.stream().mapToInt(x->x).toArray();
 
//将结果集合转为数组-法二
int[] resArr = new int[resSet.size()];
int index = 0;
for(int i : resSet1){
resArr[index++] = i;
}
 
return resArr;

 

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
            Set s = new HashSet();
            for(int i : nums1) s.add(i);
            ArrayList<Integer>  a = new ArrayList<>();
            for(int i : nums2){
                if(s.contains(i)) a.add(i);
                s.remove(i);
            }
            int[] res = new int[a.size()];
            for(int i = 0; i < res.length ; i++){
                res[i] = a.get(i);
            }
         return  res;
          
    }
}

变形 350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

 a.stream().mapToInt(Integer::intValue).toArray();

---

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i : nums1) map.put(i,map.getOrDefault(i,0)+1);
        ArrayList<Integer> a = new ArrayList<>();
        for(int i : nums2){     
            if(map.containsKey(i)&&map.get(i) >= 1 ) {
            a.add(i);
            map.put(i,map.get(i) - 1);
            }
        }
        //return a.stream().mapToInt(Integer::intValue).toArray();
        return a.stream().mapToInt(x->x).toArray();
    }
}

三、快乐数

不加set的话 直接超时
可以将判断快乐数过程中的所有点看成一个单链表，可能存在环，即该问题就变成了单链表是否存在环的问题

1、fast 指针从原点每次走2步， slow 指针从原点每次走1步
2、两个指针从起点开始走，只要有环，最终两个指针都会相遇，或者没有环，最后走到1，也会不停的在1位置循环，也会相遇，因此两个指针最后一定会相遇
(1)、当相遇的点的值是1，则表示不存在环
(2)、当相遇的点的值不是1，则表示存在环

class Solution {
    public boolean isHappy(int n) {
        // HashSet set = new HashSet<>();
        // while(n != 1  && !set.contains(n)){
        //     set.add(n);
        //     n = get(n);
        // }
        // return n==1 ;
        int fast = get(n), slow = n;
        while(fast != slow)
        {
            fast = get(get(fast));
            slow = get(slow);
        }
        return fast == 1;
       
    }
    public int get(int x ){
        int res = 0;
         while(x > 0){
             res += (x %10) * (x%10);
             x /= 10 ;
         }
         return res ;
    }
}

两数之和(梦开始的地方)

454. 四数相加 II

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int a : nums1)
            for(int b : nums2)
                map.put(a+b ,map.getOrDefault(a+b,0)+1);
        int res = 0;
        for(int c : nums3)
            for(int d : nums4) {
                int sum =(c+d) * (-1) ;
                if(map.containsKey(sum))
                res += map.get(sum);
            }
            
    return res ;

    }
}

LeetCode 15. 三数之和-java

leetcode 18. 四数之和-java

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

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

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = 0; i < n ; i ++){
            if(i > 0 && nums[i] == nums[i -1])continue;//去重
            for(int j = i+1 ; j < n ; j ++ ){
                if( j > i + 1  && nums[j] == nums[j-1])continue;
                //双指针
                for(int k = j+1 , u = n - 1 ; k < u ; k ++){
                    if(k > j + 1 && nums[k] == nums[k-1]) continue ;
                    while( k < u -1 &&(long) nums[i] + nums[j] + nums[k] + nums[u-1] >= target) u-- ;
                    if((long) nums[i] + nums[j] + nums[k] + nums[u] == target){
                        ans.add(Arrays.asList(nums[i],nums[j],nums[k],nums[u]));
                    }
                }
            }
        }
        return ans ;
    }
}