Question skimming record - hash table

Catalog

Effective alphabetic words （ Power button 242）

Intersection of two arrays （349）

Happy number （202）

Sum of two numbers

Add four numbers ||（454）

Ransom letter （383）

Sum of three numbers （15）

  Sum of four numbers （18）

---

** Generally, hash table is used to quickly determine whether an element appears in the set **

Effective alphabetic words （ Power button 242）

Given two strings s and t , Write a function to determine t Whether it is s Letter heteronym of .

```java
class Solution {
    public boolean isAnagram(String s, String t) {

        int[] record = new int[26];
        for (char c : s.toCharArray()) {
            record[c - 'a'] += 1;
        }
        for (char c : t.toCharArray()) {
            record[c - 'a'] -= 1;
        }
        for (int i : record) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }
}

```

Intersection of two arrays （349）

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        // Traversal array 1
        for (int i : nums1) {
            set1.add(i);
        }
        // Traversal array 2 To determine whether the element exists in the hash table
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        int[] resArr = new int[resSet.size()];
        int index = 0;
        // Turn the resulting geometry into an array
        for (int i : resSet) {
            resArr[index++] = i;
        }
        return resArr;
    }
}

```

Happy number （202）

Write an algorithm to judge a number n Is it a happy number .

「 Happy number 」 Defined as ： For a positive integer , Replace the number with the sum of the squares of the numbers in each of its positions , Then repeat the process until the number becomes 1, It could be Infinite loop But it doesn't change 1. If It can be 1, So this number is the happy number .

```java
// Speed pointer
class Solution {

     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;
    }
}
//

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
}

```

Sum of two numbers

```java
public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    if(nums == null || nums.length == 0){
        return res;
    }
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        int temp = target - nums[i];
        if(map.containsKey(temp)){
            res[1] = i;
            res[0] = map.get(temp);
        }
        map.put(nums[i], i);
    }
    return res;
}

```

Add four numbers ||（454）

Given a list of four arrays containing integers A , B , C , D , Calculate how many tuples there are (i, j, k, l) , bring A[i] + B[j] + C[k] + D[l] = 0.

```java
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int temp;
        int res = 0;
        // Count the sum of the elements in two arrays , At the same time, count the number of occurrences , Put in map
        for (int i : nums1) {
            for (int j : nums2) {
                temp = i + j;
                if (map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1);
                } else {
                    map.put(temp, 1);
                }
            }
        }
        // Count the sum of the remaining two elements , stay map Find out if there is an addition to 0 The situation of , Record the number of times at the same time
        for (int i : nums3) {
            for (int j : nums4) {
                temp = i + j;
                if (map.containsKey(0 - temp)) {
                    res += map.get(0 - temp);
                }
            }
        }
        return res;
    }
}

```

Ransom letter （383）

Give a ransom (ransom) String and a magazine (magazine) character string , Judge the first string ransom Can I have a second string magazines The characters inside make up . If it can be constructed , return true ; Otherwise return to false.

```java

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // Define a hash mapping array
        int[] record = new int[26];

        // Traverse
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }

        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }
        
        // If there are negative numbers in the array , explain ransomNote Strings always exist magazine Characters not in
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }
}

```

Sum of three numbers （15）

Give you one containing n Array of integers nums, Judge nums Are there three elements in a,b,c , bring a + b + c = 0 ？ Please find out all the triples that meet the conditions and do not repeat .

```java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

```

  Sum of four numbers （18）

The question ： Given an inclusion n Array of integers nums And a target value target, Judge nums Are there four elements in a,b,c and d , bring a + b + c + d The value of is equal to target equal ？ Find all quadruples that meet the conditions and are not repeated

```java
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; i++) {

            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {

                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}
```