哈希表
理论基础
什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法!
242.有效的字母异位词
leetcodde链接：242.有效的字母异位词
题目：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若?s 和 t?中每个字符出现的次数都相同，则称?s 和 t?互为字母异位词。
示例?1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
方法：哈希法
思路
本题是判断两个字符串中每个字符出现的次数是否都相同，若是则互为字母异位词。因此我们需要记录一个字符串中每个字符出现的次数，例如字符串"banana"———— a：3; b：1; n：2
我们需要记录字符及其对应的出现次数，可以使用哈希表，又由于字母最多有26个，那就可以使用长度为26的数组做哈希表，从头往后每个位置代表一个字母，每个位置的值代表字母出现次数。
一次循环记录完s每个字符出现的次数，第二次循环，将数组里t的各个字符次数一次减1，如果s和t是有效异位词，那么数组里每个值应该为0，所以最后应该遍历数组，有不为0的值，就返回false，没有就返回true。
Java代码
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;
}
}
349.两个数组的交集
leetcode链接：349.两个数组的交集
题目：
给定两个数组?nums1?和?nums2?，返回?它们的交集?。输出结果中的每个元素一定是?唯一?的。我们可以?不考虑输出结果的顺序?。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
方法：哈希法
用数组做哈希表,思路和上一题类似
Java代码
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
return new int[0];
}
//用数组做哈希表
int[] hash = new int[1005];
for(int i = 0; i < nums1.length; i++) {
hash[nums1[i]] = 1;
}
//用 HashSe t保存结果 因为不允许重复
HashSet<Integer> result = new HashSet();
for(int j = 0; j < nums2.length; j++) {
if(hash[nums2[j]] == 1) {//如果nums2的元素在hash中存在,则该元素是nums1和nums2的共同元素
//保存到 result 中
result.add(nums2[j]);
}
}
//将HashSet转为数组
int resultInt[] = new int[result.size()];
int i = 0;
for(int x : result) {
resultInt[i++] = x;
}
return resultInt;
}
}
202.快乐数
leetcode链接：202.快乐数
题目：
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」?定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为?1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入： n = 19
输出： true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入： n = 2
输出： false
方法：哈希法
看似是数学题,实际上可以用 HashMap 解决.
因为平方和要么是无限循环,要么是1,
所以用 HashMap 记录平方和, 如果重复则不是快乐数 ;
如果能变为1 则是快乐数。
Java代码
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> recode = new HashSet();
while(n != 1 && !recode.contains(n)) {
recode.add(n);
n = getnextN(n);
}
return n==1;
}
//得到下一个和的方法
private int getnextN(int n) {
int res = 0;
while(n > 0) {
int temp = (n % 10) * (n % 10);
res += temp;
n = n / 10;
}
return res;
}
}
1.两数之和
leetcode链接：1.两数之和
题目
给定一个整数数组 nums?和一个整数目标值target，请你在该数组中找出 和为目标值 target的那?两个?整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
方法：哈希法
HashMap查找、插入、删除和修改的时间复杂度都是O（1）
此方法时间复杂度为O(n)
Java代码
class Solution4 {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> hashMap = new HashMap();
//遍历数组
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];//记录target与当前元素的差值
if(hashMap.containsKey(complement)) {//如果HashMap中存在该差值
Integer res[] = {i, hashMap.get(complement)};//用Integer数组保存当前索引i和差值的索引
return new int[]{res[0],res[1]};//放入int数组并返回
}
hashMap.put(nums[i],i);//如果不存在就把当前元素的值和其索引作为一个键值对放入hashMap
}
throw new IllegalArgumentException("do not Exist");
}
}
167. 两数之和 II - 输入有序数组
leetcode链接：167. 两数之和 II - 输入有序数组
题目：
给你一个下标从 1 开始的整数数组?numbers ，该数组已按 非递减顺序排列? ，请你从数组中找出满足相加之和等于目标数?target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
当然这道题目不是使用哈希表的方法，放在这里和上一题比较。
方法：对撞指针
要巧妙利用输入的数组是有序的这一特点！！利用对撞指针可以原地进行查找。开始时左指针l指向第一个元素，右指针r指向最后一个元素。注意指针移动的条件！
Java代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length - 1;
while (l < r) {
if (numbers[l] + numbers[r] == target) {//当前和等于target 就返回
int[] res = {l + 1, r + 1};
return res;
} else if (numbers[l] + numbers[r] < target) {//当前和小于target，就让左指针向右移动一位
l++;
} else {//当前和大于target，就让右指针向左移动一位
r--;
}
}
throw new RuntimeException("error");
}
}
|