当前位置：首页 > news >正文

代码随想录之哈希表（力扣题号）

news 2025/7/3 16:04:18

242. 有效的字母异位词

在这里插入图片描述
直接用数组模拟哈希表
只有小写字母，开26的数组就可以了

class Solution {public boolean isAnagram(String s, String t) {//24-28int[] hash = new int[26];Arrays.fill(hash,0);for(int i=0;i<s.length();i++){hash[s.charAt(i)-'a']++;}for(int i=0;i<t.length();i++){hash[t.charAt(i)-'a']--;}for(int i=0;i<hash.length;i++){if(hash[i]!=0) return false;}return true;}
}

49. 字母异位词分组

在这里插入图片描述
思路也是用hashmap,但是java的操作没有很熟练，遇到很多问题，最后看了题解还是没能一次性写完，中间还看了两次，之后需要再练习几次

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//01-29Map<String, List<String>> mp= new HashMap<>();      for(int i=0;i<strs.length;i++){char[] arr = strs[i].toCharArray();Arrays.sort(arr);String key = new String(arr);List<String> list = mp.getOrDefault(key,new ArrayList<String>());list.add(strs[i]);mp.put(key,list);}return new ArrayList<List<String>>(mp.values());}
}

时间复杂度：
O(nklogk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表，因此总时间复杂度是 O(nklogk)。

空间复杂度：O(nk)，其中 n 是 strs中的字符串的数量，k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。

15 三数之和

在这里插入图片描述

这题和之前牛客做过的一样，还是一样的思路：在两数之和的基础上遍历，然后用set去重，这题不要求输出结果也排序。但是这题的数据范围更大，按照之前的写法会超时，所以加了个排序，然后如果是重复的数字就跳过遍历。

class Solution {public List<List<Integer>> threeSum(int[] nums) {//57-40Arrays.sort(nums);List<List<Integer>> res= new ArrayList<List<Integer>>();List<List<Integer>> ress= new ArrayList<List<Integer>>();for(int i=0;i<nums.length;i++){int target = -nums[i];if(i>0&&nums[i]==nums[i-1]) continue;//跳过遍历，否则会超时Map<Integer,Integer> mp = new HashMap<>();for(int j = i+1;j<nums.length;j++){if(mp.containsKey(nums[j])){List<Integer> row = new ArrayList<>();row.add(nums[i]);row.add(target-nums[j]);row.add(nums[j]);row.sort((a,b)->a-b);  res.add(row);}mp.put(target-nums[j],j);              }}Set<List<Integer>> s = new HashSet<List<Integer>>();for(int i=0;i<res.size();i++){s.add(res.get(i));}for( List<Integer> r:s){ress.add(r);}return ress;}
}

但是这样还是三重循环，时间复杂度还是N的三次方。
可以继续改进：当a+b+c=0的时候，第二层b’>b，要让条件满足的c‘一定<c,所以可以让第三层指针从右往左，和第二层的指针合并为一层，将时间复杂度降为O（N^2）

class Solution {public List<List<Integer>> threeSum(int[] nums) {//57-40Arrays.sort(nums);List<List<Integer>> res= new ArrayList<List<Integer>>();List<List<Integer>> ress= new ArrayList<List<Integer>>();for(int i=0;i<nums.length-2;i++){int target = -nums[i];if(i>0&&nums[i]==nums[i-1]) continue;Map<Integer,Integer> mp = new HashMap<>();int left = i+1;int right = nums.length-1;while(left<right){if(nums[left]+nums[right]<target) left++;else if(nums[left]+nums[right]>target) right--;else{while(left + 1 < right && nums[left] == nums[left + 1])//去重left++;while(right - 1 > left && nums[right] == nums[right - 1])//去重right--;List<Integer> row = new ArrayList<>();row.add(nums[i]);row.add(nums[left]);row.add(nums[right]);res.add(row);left++;right--;}}                         }return res;}
}

18 四数之和

在这里插入图片描述

和三数之和的思路一样，就是多了一层循环，但是四数有一个坑点在于用int会溢出，要转换成long

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {//47-04List<List<Integer>> res = new ArrayList<List<Integer>>();Arrays.sort(nums);for(int i=0;i<nums.length-3;i++){if(i>0&&nums[i]==nums[i-1]) continue;for(int j = i+1;j<nums.length-2;j++){if(j>i+1&&nums[j]==nums[j-1]) continue;int left = j+1;int right = nums.length-1;while(left<right){//注意要转换成long，否则会溢出long sum = (long)nums[i]+(long)nums[j]+(long)nums[left]+(long)nums[right];if(sum>target) right--;else if(sum<target) left++;else{List<Integer> tmp = new ArrayList<Integer>();tmp.add(nums[i]);tmp.add(nums[j]);tmp.add(nums[left]);tmp.add(nums[right]);res.add(tmp);//可以用一句解决//res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while(left<right&&nums[left+1]==nums[left]) left++;while(left<right&&nums[right-1]==nums[right]) right--;left++;right--;}}}}return res;}
}