242. 有效的字母异位词

https://leetcode-cn.com/problems/valid-anagram/

  1. public boolean isAnagram(String s, String t) {
  2.         char[] schar = s.toCharArray();
  3.         char[] tchar = t.toCharArray();
  4.         if (s.length() != t.length()) return false;
  6.         int[] count = new int[26];
  7.         for (int i = 0; i < schar.length; i++) {
  8.             count[schar[i] - 'a']++;
  9.         }
  10.         for (int i = 0; i < tchar.length; i++) {
  11.             if (--count[tchar[i] - 'a'] < 0) {
  12.                 return false;
  13.             }
  14.         }
  15.         return true;
  16. }

383. 赎金信

https://leetcode-cn.com/problems/ransom-note/

  1.  public boolean canConstruct(String ransomNote, String magazine) {
  2.          char[] str1 = ransomNote.toCharArray();
  3.          char[] str2 = magazine.toCharArray();
  4.          int[] count = new int[26];
  6.          for (int i = 0; i < str2.length; i++) {
  7.              count[str2[i] - 'a']++;
  8.          }
  10.          for (int i = 0; i < str1.length; i++) {
  11.              count[str1[i] - 'a']--;
  12.          }
  14.          for (int i : count) {
  15.              if (i < 0) {
  16.                  return false;
  17.              }
  18.          }
  19.          return true;
  21.  }

49. 字母异位词分组

https://leetcode-cn.com/problems/group-anagrams/

  • 排序

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键

  1.  public List<List<String>> groupAnagrams(String[] strs) {
  2.         Map<String, List<String>> map = new HashMap<>();
  3.         for (String str : strs) {
  4.             char[] chs = str.toCharArray();
  5.             Arrays.sort(chs);
  6.             String key = String.valueOf(chs);
  7.             if (!map.containsKey(key)) {
  8.                 map.put(key, new ArrayList<>());
  9.             }
  10.             map.get(key).add(str);
  11.         }
  12.         List<List<String>> res = new ArrayList<>();
  13.         for (List<String> list : map.values()) {
  14.             res.add(list);
  15.         }
  16.         return res;
  17.     }

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

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

  • 滑动窗口 + 欠帐表 + 总账目

https://www.yuque.com/docs/share/38e3c359-548d-4304-be67-dab91724041a?# 

  1.     public List<Integer> findAnagrams(String s, String p) {
  2.         List<Integer> ans = new ArrayList<>();
  3.         if (s == null || p == null || s.length() < p.length()) {
  4.             return ans;
  5.         }
  6.         char[] str = s.toCharArray();
  7.         char[] ptr = p.toCharArray();
  8.         int N = str.length;
  9.         int M = ptr.length;
  11.         // 欠帐表
  12.         Map<Character, Integer> map = new HashMap<>();
  13.         // 总账目
  14.         int all = M;
  16.         // 欠帐表初始化
  17.         for (char c : ptr) {
  18.             if (map.containsKey(c)) {
  19.                 map.put(c, map.get(c) + 1);
  20.             } else {
  21.                 map.put(c, 1);
  22.             }
  23.         }
  25.         for (int i = 0; i < M - 1; i++) {
  26.             if (map.containsKey(str[i])) {
  27.                 int count = map.get(str[i]);
  28.                 map.put(str[i], count - 1);
  29.                 if (count > 0) {
  30.                     all--;
  31.                 }
  32.             }
  33.         }
  35.         for (int end = M - 1, start = 0; end < N; end++, start++) {
  36.             if (map.containsKey(str[end])) {
  37.                 int count = map.get(str[end]);
  38.                 map.put(str[end], count - 1);
  39.                 if (count > 0) {
  40.                     all--;
  41.                 }
  42.             }
  44.             if (all == 0) {
  45.                 ans.add(start);
  46.             }
  48.             if (map.containsKey(str[start])) {
  49.                 int count = map.get(str[start]);
  50.                 map.put(str[start], count + 1);
  51.                 if (count >= 0) {
  52.                     all++;
  53.                 }
  54.             }
  55.         }
  56.         return ans;
  57.     }

349. 两个数组的交集

  1.  public int[] intersection(int[] nums1, int[] nums2) {
  2.         Set<Integer> set = new HashSet();
  3.         Set<Integer> set1 = new HashSet();
  5.         for (int i : nums1) {
  6.             set.add(i);
  7.         }
  9.         for (int i : nums2) {
  10.             if (set.contains(i)) {
  11.                 set1.add(i);
  12.             }
  13.         }
  15.         int[] ans = new int[set1.size()];
  16.         int index = 0;
  17.         for (int i : set1) {
  18.             ans[index++] = i;
  19.         }
  20.         return ans;
  21.     }

350. 两个数组的交集Ⅱ

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/

  1.  public int[] intersect(int[] nums1, int[] nums2) {
  2.         Map<Integer, Integer> map = new HashMap<>();
  3.         for (int i : nums1) {
  4.             if (!map.containsKey(i)) {
  5.                 map.put(i, 1);
  6.             } else {
  7.                 map.put(i, map.get(i) + 1);
  8.             }
  9.         }
  10.         List<Integer> list = new ArrayList<>();
  11.         for (int i : nums2) {
  12.             if (map.containsKey(i) && map.get(i) >= 1) {
  13.                 list.add(i);
  14.                 map.put(i, map.get(i) - 1);
  15.             } else {
  16.                 continue;
  17.             }
  18.         }
  19.         int[] ans = new int[list.size()];
  20.         int index = 0;
  21.         for (int i : list) {
  22.             ans[index++] = i;
  23.         }
  24.         return ans;
  25.     }

202. 快乐数

https://leetcode-cn.com/problems/happy-number/
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

  1.  public boolean isHappy(int n) {
  2.         HashSet<Integer> set = new HashSet<>();
  3.         while (n != 1) {
  4.             int sum = 0;
  5.             while (n != 0) {
  6.                 sum += Math.pow(n % 10, 2);
  7.                 n /= 10;
  8.             }
  9.             n = sum;
  10.             if (set.contains(n)) {
  11.                 break;
  12.             }
  13.             set.add(n);
  14.         }
  15.         return n == 1;
  17. }

5. 两数之和

https://leetcode-cn.com/problems/two-sum/

  1.    public int[] twoSum(int[] nums, int target) {
  2.         Map<Integer, Integer> map = new HashMap<>();
  3.         for (int i = 0; i < nums.length; i++) {
  4.             if (map.containsKey(target - nums[i])) {
  5.                 return new int[]{map.get(target - nums[i]), i};
  6.             }
  7.             map.put(nums[i], i);
  8.         }
  9.         return new int[]{-1, -1};
  10.     }

454. 四数相加Ⅱ

https://leetcode-cn.com/problems/4sum-ii/

  1.    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
  2.         HashMap<Integer, Integer> map = new HashMap<>();
  3.         int ans = 0;
  5.         for (int i = 0; i < nums1.length; i++) {
  6.             for (int j = 0; j < nums2.length; j++) {
  7.                 int sum = nums1[i] + nums2[j];
  8.                 if (map.containsKey(sum)) {
  9.                     map.put(sum, map.get(sum) + 1);
  10.                 } else {
  11.                     map.put(sum, 1);
  12.                 }
  13.             }
  14.         }
  16.         for (int i = 0; i < nums3.length; i++) {
  17.             for (int j = 0; j < nums4.length; j++) {
  18.                 int sum = nums3[i] + nums4[j];
  19.                 if (map.containsKey(-sum) && map.get(-sum) > 0) {
  20.                     ans += map.get(-sum);
  21.                 }
  22.             }
  23.         }
  24.         return ans;
  25.     }

15. 三数之和

https://leetcode-cn.com/problems/3sum/
排序+ 双指针
哈希表专题 - 图1

  1.   public List<List<Integer>> threeSum(int[] nums) {
  2.         // 排序
  3.         Arrays.sort(nums);
  4.         List<List<Integer>> ans = new ArrayList<>();
  6.         for (int i = 0; i < nums.length; i++) {
  7.             if (i == 0 || nums[i] != nums[i - 1]) { // 去重
  8.                 List<LinkedList<Integer>> nexts = twoSum(nums, i + 1, -nums[i]);
  9.                 for (LinkedList<Integer> next : nexts) {
  10.                     next.addFirst(nums[i]);
  11.                     ans.add(next);
  12.                 }
  13.             }
  14.         }
  15.         return ans;
  16.     }
  18.     // nums是排好序的
  19.     private List<LinkedList<Integer>> twoSum(int[] nums, int begin, int target) {
  20.         List<LinkedList<Integer>> ans = new ArrayList<>();
  21.         int L = begin;
  22.         int R = nums.length - 1;
  23.         while (L < R) {
  24.             if (nums[L] + nums[R] > target) {
  25.                 R--;
  26.             } else if (nums[L] + nums[R] < target) {
  27.                 L++;
  28.             } else {
  29.                 if (L == begin || nums[L - 1] != nums[L]) { // 去重
  30.                     LinkedList<Integer> cur = new LinkedList<>();
  31.                     cur.add(nums[L]);
  32.                     cur.add(nums[R]);
  33.                     ans.add(cur);
  34.                 }
  35.                 L++;
  36.             }
  38.         }
  39.         return ans;
  40.     }

18. 四数之和

https://leetcode-cn.com/problems/4sum/

  1.  public List<List<Integer>> fourSum(int[] nums, int target) {
  2.         // 排序
  3.         Arrays.sort(nums);
  4.         List<List<Integer>> ans = new ArrayList<>();
  5.         for (int i = 0; i <= nums.length - 4; i++) {
  6.             if (i == 0 || nums[i] != nums[i - 1]) { //去重
  7.                 List<LinkedList<Integer>> nexts = threeSum(nums, i + 1, target - nums[i]);
  8.                 for (LinkedList<Integer> next : nexts) {
  9.                     next.addFirst(nums[i]);
  10.                     ans.add(next);
  11.                 }
  12.             }
  13.         }
  14.         return ans;
  15.     }
  17.     private List<LinkedList<Integer>> threeSum(int[] nums, int begin, int target) {
  18.         List<LinkedList<Integer>> ans = new ArrayList<>();
  19.         for (int i = begin; i <= nums.length - 3; i++) {
  20.             if (i == begin || nums[i] != nums[i - 1]) {
  21.                 List<LinkedList<Integer>> nexts = twoSum(nums, i + 1, target - nums[i]);
  22.                 for (LinkedList<Integer> next : nexts) {
  23.                     next.addFirst(nums[i]);
  24.                     ans.add(next);
  25.                 }
  26.             }
  27.         }
  28.         return ans;
  29.     }
  31.     // nums是排好序的
  32.     private List<LinkedList<Integer>> twoSum(int[] nums, int begin, int target) {
  33.         List<LinkedList<Integer>> ans = new ArrayList<>();
  34.         int L = begin;
  35.         int R = nums.length - 1;
  36.         while (L < R) {
  37.             if (nums[L] + nums[R] > target) {
  38.                 R--;
  39.             } else if (nums[L] + nums[R] < target) {
  40.                 L++;
  41.             } else {
  42.                 if (L == begin || nums[L] != nums[L - 1]) {
  43.                     LinkedList<Integer> cur = new LinkedList<>();
  44.                     cur.add(nums[L]);
  45.                     cur.add(nums[R]);
  46.                     ans.add(cur);
  47.                 }
  48.                 L++;
  49.             }
  50.         }
  51.         return ans;
  52.     }