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;ihash[s.charAt(i)-'a']++;}for(int i=0;ihash[t.charAt(i)-'a']--;}for(int i=0;iif(hash[i]!=0) return false;}return true;}
}

49. 字母异位词分组

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

class Solution {public List> groupAnagrams(String[] strs) {//01-29Map> mp= new HashMap<>();      for(int i=0;ichar[] arr = strs[i].toCharArray();Arrays.sort(arr);String key = new String(arr);List list = mp.getOrDefault(key,new ArrayList());list.add(strs[i]);mp.put(key,list);}return new ArrayList>(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> threeSum(int[] nums) {//57-40Arrays.sort(nums);List> res= new ArrayList>();List> ress= new ArrayList>();for(int i=0;iint target = -nums[i];if(i>0&&nums[i]==nums[i-1]) continue;//跳过遍历，否则会超时Map mp = new HashMap<>();for(int j = i+1;jif(mp.containsKey(nums[j])){List 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> s = new HashSet>();for(int i=0;is.add(res.get(i));}for( List r:s){ress.add(r);}return ress;}
}

但是这样还是三重循环，时间复杂度还是N的三次方。
可以继续改进：当a+b+c=0的时候，第二层b’>b，要让条件满足的c‘一定

class Solution {public List> threeSum(int[] nums) {//57-40Arrays.sort(nums);List> res= new ArrayList>();List> ress= new ArrayList>();for(int i=0;iint target = -nums[i];if(i>0&&nums[i]==nums[i-1]) continue;Map mp = new HashMap<>();int left = i+1;int right = nums.length-1;while(leftif(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 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> fourSum(int[] nums, int target) {//47-04List> res = new ArrayList>();Arrays.sort(nums);for(int i=0;iif(i>0&&nums[i]==nums[i-1]) continue;for(int j = i+1;jif(j>i+1&&nums[j]==nums[j-1]) continue;int left = j+1;int right = nums.length-1;while(left//注意要转换成long，否则会溢出long sum = (long)nums[i]+(long)nums[j]+(long)nums[left]+(long)nums[right];if(sum>target) right--;else if(sumList tmp = new ArrayList();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