当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法
1.Java HashMap getOrDefault() 方法
import java.util.HashMap;
class Main {
public static void main(String[] args) {
// 创建一个 HashMap
HashMap<Integer, String> sites = new HashMap<>();
// 往 HashMap 添加一些元素
sites.put(1, "Google");
sites.put(2, "Runoob");
// key 的映射存在于 HashMap 中
// Not Found - 如果 HashMap 中没有该 key，则返回默认值
String value1 = sites.getOrDefault(1, "Not Found");
System.out.println("Value for key 1: " + value1);
// key 的映射不存在于 HashMap 中
// Not Found - 如果 HashMap 中没有该 key，则返回默认值
String value2 = sites.getOrDefault(4, "Not Found");
System.out.println("Value for key 4: " + value2);
}
}
Value for key 1: Google
Value for key 4: Not Found
2.力扣49-字母异位词分组-哈希表
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if(strs == null || strs.length == 0){
return new ArrayList();
}
//创建一个哈希表
Map<String, List> map = new HashMap<String,List>();
for(String s: strs){
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
//判断哈希表中是否已有该key值
if(!map.containsKey(key)){
map.put(key,new ArrayList());
}
//将该字符串放在对应的key的list中
map.get(key).add(s);
}
//返回map中所有键值对象构成的list
return new ArrayList(map.values());
}
}
3.力扣438-找到字符串中所有的字符异位词-滑动窗口
class Solution {
public static boolean check(int[] a, int[] b){
for(int i = 0; i < 26; i ++){
if(a[i] != b[i]) return false;
}
return true;
}
public List<Integer> findAnagrams(String s, String p) {
List<Integer> ans = new ArrayList<>();
int n = s.length(), m = p.length();
int[] c1 = new int[26], c2 = new int[26];
for(int i = 0; i < m; i ++){
c2[p.charAt(i) - 'a'] ++;
}
for(int l = 0, r = 0; r < n; r ++){
c1[s.charAt(r) - 'a'] ++;
if(r - l + 1 > m) c1[s.charAt(l ++) - 'a'] --;
if(check(c1, c2)) ans.add(l);
}
return ans;
}
}
4.将结果集合转为数组
Set
int[]
return resSet.stream().mapToInt(x -> x).toArray();
5.一些规范
6.力扣349、350-两个数组的交集
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1.length == 0 || nums1 == null || nums2 == null || nums2.length == 0)
return new int[0];
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for(int i :nums1){
set1.add(i);
}
for(int j :nums2){
if(set1.contains(j)){
set2.add(j);
}
}
return set2.stream().mapToInt(x -> x).toArray();
}
}
5.关于Arrays.copyOfRange()方法的使用
用于对一个已有的数组进行截取复制，复制出一个左闭右开区间的数组。
6.该方法是将数组转化成List集合的方法。
List
7.力扣15-三数之和-双指针、一层循环
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i ++){
if(nums[i] > 0) return result;//每次循环，如果第一个数就大于0，那么就可以结束循环了
if(i > 0 && nums[i] == nums[i - 1]) continue;//第一个数去重（从第二个数开始，如果和前面一 样，就可以结束这一次循环了
int left = i + 1;
int right = nums.length - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0) right --;
else if (sum < 0) left ++;
else{
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
left ++;
right --;
while(right > left && nums[right] == nums[right + 1]) right --;
while(left < right && nums[left] == nums[left - 1]) left ++;
}
}
}
return result;
}
}
8.力扣18-四数之和-双指针、两层循环嵌套
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i ++){
if(nums[i] > 0 && nums[i] > target) return result;
if(i > 0 && nums[i - 1] == nums[i]) continue;
for(int j = i + 1; j < nums.length; j ++){
if(j > i + 1 && nums[j - 1] == nums[j]) continue;
int left = j + 1;
int right = nums.length - 1;
while(left < right){
long sum = (long)(nums[i] + nums[j] + nums[left] + nums[right]);
if(sum > target) right --;
else if(sum < target) left ++;
else{
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left ++;
right --;
while(left < right && nums[left - 1] == nums[left]) left ++;
while(right > left && nums[right + 1] == nums[right]) right --;
}
}
}
}
return result;
}
}