目录
- 1. 两数之和(*)
- 242. 有效的字母异位词(easy)
- 49. 字母异位词分组(*)
- 349. 两个数组的交集
- 202. 快乐数(1.使用Set存哈希，2.快慢指针)
- 454. 四数相加 II
- 383. 赎金信
- 15. 三数之和*(双指针)
- 18. 四数之和*(双指针)
- 128. 最长连续序列
1. 两数之和(*)
https://leetcode.cn/problems/two-sum/
使用map存储遍历过的数组中的值，每遍历到一个元素，就去map集合中查找有没有值为（target-num[i]）的元素。
map的key存储数组元素的值，value存储数组元素的下标。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer>map=new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
return new int[]{i,map.get(target-nums[i])};
}
map.put(nums[i],i);
}
return null;
}
}
242. 有效的字母异位词(easy)
https://leetcode.cn/problems/group-anagrams/
class Solution {
public boolean isAnagram(String s, String t) {
int hash[]=new int[26];
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<26;i++){
if(hash[i]!=0){
return false;
}
}
return true;
}
}
49. 字母异位词分组(*)
https://leetcode.cn/problems/group-anagrams/
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
//方法一：排序
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 创建一个哈希映射，键是排序后的字符串，值是所有对应的异位词
Map<String, List<String>> map = new HashMap<String, List<String>>();
// 遍历输入的字符串数组
for (String str : strs) {
// 将当前字符串转换为字符数组
char[] array = str.toCharArray();
// 对字符数组进行排序
Arrays.sort(array);
// 将排序后的字符数组转换回字符串，作为哈希映射的键
String key = new String(array);
// 从哈希映射中获取键对应的异位词列表，如果不存在则返回一个新的列表
List<String> list = map.getOrDefault(key, new ArrayList<String>());
// 将当前字符串添加到异位词列表中
list.add(str);
// 将异位词列表放回哈希映射中
map.put(key, list);
}
// 将哈希映射中的所有值（即所有的异位词列表）转换为一个列表返回
return new ArrayList<List<String>>(map.values());
}
方法一：计数： `
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 262626 的数组记录每个字母出现的次数。需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 创建一个哈希映射，键是字符计数字符串，值是所有对应的异位词
Map<String, List<String>> map = new HashMap<String, List<String>>();
// 遍历输入的字符串数组
for (String str : strs) {
// 创建一个长度为26的数组，用于记录每个字符的出现次数
int[] counts = new int[26];
int length = str.length();
// 遍历当前字符串，更新字符计数数组
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 创建一个字符串缓冲区，用于构建字符计数字符串
StringBuffer sb = new StringBuffer();
// 遍历字符计数数组，将每个出现次数大于0的字符和出现次数按顺序拼接成字符串
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[i]);
}
}
// 将字符计数字符串作为哈希映射的键
String key = sb.toString();
// 从哈希映射中获取键对应的异位词列表，如果不存在则返回一个新的列表
List<String> list = map.getOrDefault(key, new ArrayList<String>());
// 将当前字符串添加到异位词列表中
list.add(str);
// 将异位词列表放回哈希映射中
map.put(key, list);
}
// 将哈希映射中的所有值（即所有的异位词列表）转换为一个列表返回
return new ArrayList<List<String>>(map.values());
}
349. 两个数组的交集
https://leetcode.cn/problems/intersection-of-two-arrays/
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> resSet=new HashSet<>();
Set<Integer> set=new HashSet<>();
for(int i:nums1){
set.add(i);
}
for(int i:nums2){
if(set.contains(i)){
resSet.add(i);
}
}
int j=0;
int []arr=new int[resSet.size()];
for(int i:resSet){
arr[j++]=i;
}
return arr;
}
}
202. 快乐数(1.使用Set存哈希，2.快慢指针)
https://leetcode.cn/problems/happy-number/
class Solution {
public boolean isHappy(int n) {
//方法一：使用SetHash检测循环
Set<Integer> set=new HashSet<>();
while(n!=1 && !set.contains(n)){
set.add(n);
n=getNextNumber(n);
}
return n==1;
//方法二：使用快慢指针检测循环
// int fast=getNextNumber(n);
// int slow=n;
// while(fast!=1 && fast!=slow){
// slow=getNextNumber(slow);
// fast=getNextNumber(getNextNumber(fast));
// }
// return fast==1;
}
//将n替换为它每个位置上的数字的平方和。
private int getNextNumber(int n) {
int res = 0;
while (n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}
454. 四数相加 II
https://leetcode.cn/problems/4sum-ii/
我们可以将四个数组分成两部分，A和 B 为一组，C 和 D 为另外一组。
对于 A 和 B，我们使用二重循环对它们进行遍历，得到所有 A[i]+B[j] 的值并存入哈希映射中。对于哈希映射中的每个键值对，每个键表示一种 A[i]+B[j]，对应的值为 A[i]+B[j] 出现的次数。
对于 C 和 D，我们同样使用二重循环对它们进行遍历。当遍历到 C[k]+D[l]时，如果 −( C[k]+D[l] )出现在哈希映射中，那么将 −(C[k]+D[l]) 对应的值累加进答案中。
最终即可得到满足 A[i]+B[j]+C[k]+D[l]=0 的四元组数目。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i : nums1) {
for (int j : nums2) {
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
for (int i : nums3) {
for (int j : nums4) {
res += map.getOrDefault(0 - i - j, 0);
}
}
return res;
}
}
383. 赎金信
https://leetcode.cn/problems/ransom-note/
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()){
return false;
}
int []hash=new int[26];
for(char ch : magazine.toCharArray()){
hash[ch-'a']++;
}
for(char ch : ransomNote.toCharArray()){
hash[ch-'a']--;
}
for(int i=0;i<26;i++){
if(hash[i]<0){
return false;
}
}
return true;
}
}
15. 三数之和*(双指针)
https://leetcode.cn/problems/3sum/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
return res;
}
if(i>0 && nums[i]==nums[i-1]){ //去重
continue;
}
int left=i+1;
int right=nums.length-1;
while(left<right){
if(nums[i]+nums[left]+nums[right]>0){
right--;
}else if(nums[i]+nums[left]+nums[right]<0){
left++;
}else{
List<Integer> list=new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
res.add(list);
while(left<right && nums[right]==nums[right-1]){
right--;
}
while(left<right && nums[left]==nums[left+1]){
left++;
}
right--;
left++;
}
}
}
return res;
}
}
18. 四数之和*(双指针)
https://leetcode.cn/problems/4sum/
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i]>0 && nums[i]>target){//剪枝
return res;
}
if(i>0 && nums[i]==nums[i-1]){ //去重
continue;
}
for(int j=i+1;j<nums.length;j++){
if(j>i+1 && nums[j]==nums[j-1]){ //去重
continue;
}
int left=j+1;
int right=nums.length-1;
while(left<right){
if(nums[i]+nums[j]+nums[left]+nums[right]>target){
right--;
}else if(nums[i]+nums[j]+nums[left]+nums[right]<target){
left++;
}else{
List<Integer> list=new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
res.add(list);
while(left<right && nums[right]==nums[right-1]){
right--;
}
while(left<right && nums[left]==nums[left+1]){
left++;
}
right--;
left++;
}
}
}
}
return res;
}
}
128. 最长连续序列
https://leetcode.cn/problems/longest-consecutive-sequence/
class Solution {
public int longestConsecutive(int[] nums) {
int res = 0; // 记录最长连续序列的长度
Set<Integer> numSet = new HashSet<>(); // 记录所有的数值
for(int num: nums){
numSet.add(num); // 将数组中的值加入哈希表中
}
int seqLen; // 连续序列的长度
for(int num: numSet){
// 如果当前的数是一个连续序列的起点，统计这个连续序列的长度
if(!numSet.contains(num - 1)){
seqLen = 1;
while(numSet.contains(++num))seqLen++; // 不断查找连续序列，直到num的下一个数不存在于数组中
res = Math.max(res, seqLen); // 更新最长连续序列长度
}
}
return res;
}
}
