哈希表类型

发表于 更新于 分类于 阅读次数： Valine：

哈希表类型

有效的字母异位词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean isAnagram(String s, String t) {
    //英文字母只有26个，所以我们定义26个
    int[] array =new int[26];
    for (char qs:s.toCharArray()){
        array[qs-'a']+=1;
    }
    for (char qs:t.toCharArray()){
        array[qs-'a']-=1;
    }
    for (int i:array){
        if (i!=0){
            return false;
        }
    }
    return true;
}

在这里我们不一定要使用Java提供的hascode方法，我们这里相当于自己重写了hascode方法，使得数组的不同位置可以代表不同的数

两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

使用set接口提供

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] intersection(int[] nums1, int[] nums2) {
    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);
        }
    }
    int []arr=new int[set2.size()];
    int j=0;
    for (int i:set2){
        arr[j++]=i;
    }
    return arr;
}

排序+双指针

  • 思路：数组排序，然后用两个指针分别遍历数组，如果两个指针指向的元素相等 就是其中一个交集，否则比较两个指针指向的元素的大小，较小的向前移动
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[] intersection(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    ArrayList<Integer> arrayList=new ArrayList<>();
    int index2=0;
    for (int index1=0;index1<nums1.length&&index2<nums2.length;){
        if (nums1[index1]==nums2[index2]){
            if (!arrayList.contains(nums1[index1])){
                arrayList.add(nums1[index1]);
            }
            index1++;
            index2++;
        }else if (nums1[index1]<nums2[index2]){
            index1++;
        }else {
            index2++;
        }
    }
    int []arr=new int[arrayList.size()];
    int j=0;
    for (int i:arrayList){
        arr[j]=i;
        j++;
    }
    return arr;
}

这里调用了Java提供的集合类，其实这里不进行调用也可以进行操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[length1 + length2];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                // 保证加入元素的唯一性
                if (index == 0 || num1 != intersection[index - 1]) {
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}

快乐数

202. 快乐数 - 力扣（LeetCode）

其实这道题目拥有三种可能，结果为1，得到循环，数值接近无穷大，而其实数值接近无穷大是不能存在的，快乐数 - 快乐数 - 力扣（LeetCode），我们知道n的范围，而且9的平方是十个数中值最大的，我们寻找出最大值n其实可以最大可以表示10位数，但是表示不到10个9，这里我们采用9999999999表示最大数，第一次进行运算之后

递归

image-20220615093328977 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//这里使用递归进行运算，但是这样会造成栈空间的溢出，所以可以使用循环来代替
public boolean isHappy(int n) {
    ArrayList<Integer> arrayList=new ArrayList<>();
    int sum=0;
    int a=n;
    arrayList.add(n);
    while (n!=0){
        int temp=n%10;
        n=n/10;
        sum=sum+temp*temp;
    }
    if (sum==1){
        return true;
    }
    if (arrayList.contains(sum)){
        return false;
    }
    return isHappy(sum);
}

集合

这是循环的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isHappy(int n) {
    ArrayList<Integer> arrayList=new ArrayList<>();
    int sum=n;
    arrayList.add(n);
    while (sum!=1) {
        n=sum;
        sum=0;
        while (n != 0) {
            int temp = n % 10;
            n = n / 10;
            sum = sum + temp * temp;
        }
        if (arrayList.contains(sum)){
            return false;
        }else {
            arrayList.add(sum);
        }
    }
    return true;
}

双指针

快乐数 - 快乐数 - 力扣（LeetCode）

其实这里面有一个双指针的方法证明存在环形结构，这里其实模拟了一个单链表，只不过我们改变了单链表的next域的指向规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }

    public boolean isHappy(int n) {
        int slowRunner = n;
        int fastRunner = getNext(n);
        while (fastRunner != 1 && slowRunner != fastRunner) {
            slowRunner = getNext(slowRunner);
            fastRunner = getNext(getNext(fastRunner));
        }
        return fastRunner == 1;
}

两数之和

暴力排序

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int []a = new int[2];
        for(int i=0;i< nums.length;i++)
            for(int k=i+1;k< nums.length;k++)
                if(nums[i]+nums[k]==target)
                {a[0]=i;a[1]=k;}
        
                 return a;   
    }
}

使用Hashmap1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[] twoSum(int[] nums, int target) {
        HashMap<Integer ,Integer> hashMap=new HashMap<>();
        for (int i=0;i<nums.length;i++){
            hashMap.put(i,nums[i]);
        }
        int index1=0;
        int index2=0;
        for (int i=0;i<nums.length;i++){
            int temp=target-nums[i];
            hashMap.remove(i);
            if (hashMap.containsValue(temp)){
                index1=i;
                index2=getKey(hashMap,temp);
            }
        }
        return new int[]{index1,index2};
    }

    public int getKey(HashMap<Integer,Integer> hashMap,Integer value){
        for (Integer key: hashMap.keySet()){
            if (hashMap.get(key).equals(value)){
                return key;
            }
        }
        return -1;
    }

使用Hashmap2

这里使用的是将num数组的值作为key，而数组的下标作为value，因为结果将要返回的是数组的下标，而将数组的下标作为值，可以轻松得到值，而不用使用另外的方法去寻找相关发键

1
2
3
4
5
6
7
8
9
10
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; ++i) {
        if (hashtable.containsKey(target - nums[i])) {
            return new int[]{hashtable.get(target - nums[i]), i};
        }
        hashtable.put(nums[i], i);
    }
    return new int[0];
}

四数之和

454. 四数相加 II - 力扣（LeetCode）

对于四个数相加，我们可以先分成两组，每一组中组成的数是两个数组的和，同时设置一个专门用记录一组中一个个数的的数

基础做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.HashMap;
import java.util.Set;

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //在这个中我们使用hashmap，而对于这个形成值的个数是改变的，所以这个值作为hasmap的值而不是键
        HashMap<Integer,Integer> hashMap1=new HashMap<>();
        HashMap<Integer,Integer> hashMap2=new HashMap<>();

        traverseArray(nums1,nums2,hashMap1);
        traverseArray(nums3,nums4,hashMap2);

        int count=0;
        Set<Integer> keySet1=hashMap1.keySet();
        Set<Integer> keySet2=hashMap2.keySet();
        for (Integer key:keySet1){
            int temp= -key;
            if (keySet2.contains(temp)){
                count=count+hashMap2.get(temp)*hashMap1.get(key);
            }
        }

        return count;

    }
    public void traverseArray(int[] nums1, int[] nums2,HashMap<Integer,Integer> hashMap){
        for (int j : nums1) {
            for (int k : nums2) {
                int num = j + k;
                //如果存在，则+1
                if (hashMap.containsKey(num)) {
                    int a = hashMap.get(num) + 1;
                    hashMap.put(num, a);
                    //如果不存在，则直接添加
                } else {
                    hashMap.put(num, 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        int []num1=new int[]{-1,-1};
        int []num2=new int[]{-1,1};
        int []num3=new int[]{-1,1};
        int []num4=new int[]{1,-1};
        Solution solution=new Solution();
        solution.fourSumCount(num1,num2,num3,num4);
    }
}

官方做法

官方思路与上述的相同，但是效率却很不同，原来第二次我们就可以不使用再次进行遍历，在这里已经可以直接对这个值相加是否为0进行判断，而且getOrDefault可以直接是我们少很多步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }


}

赎金信

383. 赎金信 - 力扣（LeetCode）

基础解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (char a : magazine.toCharArray()) {
            hashMap.put(a, hashMap.getOrDefault(a, 0) + 1);
        }
        for (char a:ransomNote.toCharArray()) {
            if (hashMap.containsKey(a)) {
                hashMap.put(a, hashMap.get(a) - 1);
            }else {
                return false;
            }
            if (hashMap.containsValue(-1)){
                return false;
            }
        }
        return true;
    }
}

先将magazine存入数组，然后在一个一个进行查找检测，遇到-1。则说明不够，直接false

巧妙自造hash规则

因为这个存放的是26位字母，数量可数，数组的大小的也确定，根据26个字母对应的ascii值，得到对应的位置，而对应的位置中存储的是重复的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] array = new int[26];
        for (char a : magazine.toCharArray()) {
            array[a - 'a']++;
        }
        for (char a : ransomNote.toCharArray()) {
            if (--array[a - 'a'] == -1) {
                return false;
            }
        }
        return true;

    }
}

image-20220705211313343

分析

其实就算法的复杂度上，这两个方法都是m+n级别，但是最终的执行速度结果差别很大。而对比这道题和四数之和这道题，其实思路差不多，但是四数之和不进行自定义hashcode值的方式，是因为这个值的多少与大小无法确定，但是这道题目却可以确定定制的hash数组的大小等等。

三树之和

15. 三数之和 - 力扣（LeetCode）

下面是leetcode给出的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

下面是我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> listList = new ArrayList<>();
        if (nums.length < 3) {
            return listList;
        }
        //首先进行排序
        Arrays.sort(nums);
        int length = nums.length;

        for (int i = 0; i < length; i++) {
            if (i!=0){
                if (nums[i]==nums[i-1]){
                    continue;
                }
            }
            int temp1 = -nums[i];
            int lowIndex = i + 1;
            for (; lowIndex < length; lowIndex++) {
                int fastIndex = lowIndex + 1;
                boolean flag=false;
                if (fastIndex>=length){
                    continue;
                }
                int temp2 = temp1 - nums[lowIndex];
                while (temp2 != nums[fastIndex]) {
                    fastIndex++;
                    if (fastIndex>=length){
                        flag=true;
                        break;
                    }
                }
                if (flag){
                    continue;
                }
                if (nums[fastIndex] == temp2) {
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    arrayList.add(nums[i]);
                    arrayList.add(nums[lowIndex]);
                    arrayList.add(nums[fastIndex]);
                    if (!listList.contains(arrayList)) {
                        listList.add(arrayList);
                    }
                }
            }
        }
        return listList;
    }
}

这两个思路完全相同，而且大部分的测试用例都可以通过，但是我的代码最终超出时间限制了，但是他对排序后的条件再一次进行了使用，判断出最终的值是否在应该排序的范围内部，减少了不必要的无效重复循环。