[toc]

Hash

Overview

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

hashmap

hashset

242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] dict = new int[26];
        for(int i = 0 ; i < s.length(); i++){
            char temp = s.charAt(i);
            dict[temp - 'a'] ++;
        }
        for(int i = 0 ; i < t.length(); i++){
            char temp = t.charAt(i);
            dict[temp - 'a'] --;
        }
        for(int i : dict){
            if(i != 0) return false;
        }
        return true;
    }
}

349. Intersection of Two Arrays

Easy

Given two integer arrays nums1 and nums2, return an array of their

intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        HashSet<Integer> temp = new HashSet<>();
        HashSet<Integer> res = new HashSet<>();
        for(int i : nums1){
            temp.add(i);
        }
        for(int i : nums2){
            if(temp.contains(i)){
                res.add(i);
            }
        }
        int[] ans = new int[res.size()];
        int j = 0;
        for(int i : res){
            ans[j] = i;
            j++;
        }
        return ans;
    }
}

202. Happy Number

Easy

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

1
2
3
4
5
6
7
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
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
class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> dic = new HashSet<>();
        while(n != 1){
            if(dic.contains(n) ){
                return false;
            }else{
                dic.add(n);
            }
            int add = 0;
            int current = n;
            while(current > 0){
                add += (current%10) * (current%10); 
                /*
                its wrong to say 
                add += current%10 * current%10; 
                */
                current = current/10;
            }
           if(add == 1) return true;
            n = add;
            
        }
        return true;
        
    }
}

1. Two Sum

Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have *exactly* one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> res = new HashMap<>();
        for(int i = 0 ; i < nums.length; i++){
            int add = target - nums[i];
            if(res.containsKey(add)){
                return new int[]{res.get(add), i};
            }
            res.put(nums[i], i);
        }
        return new int[]{0};

    }
}

454. 4Sum II

Medium

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:

1
2
3
4
5
6
Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i : nums1){
            for(int j : nums2){
                map.put(i + j , map.getOrDefault(i+j , 0)+1);
            }
        }
        int res = 0;
        for(int i : nums3){
            for(int j : nums4){
                res += map.getOrDefault(- i - j , 0);
            }
        }
        return res;
    }
}

✨ you dont need two hashmaps for this question

383. Ransom Note

Easy

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

1
2
Input: ransomNote = "a", magazine = "b"
Output: false
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[] dict = new int[26];
        for(int i = 0 ; i < magazine.length(); i++){
            char temp = magazine.charAt(i);
            dict[temp - 'a'] ++;
        }
        for(int i = 0 ; i < ransomNote.length(); i++){
             char temp = ransomNote.charAt(i);
             dict[temp - 'a'] --;
             if( dict[temp - 'a'] < 0) return false;
        }
        return true;
    }
}

15. 3Sum

😭 要考虑去重问题的话就用 two pointers

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

1
2
3
4
5
6
7
8
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>>res = new LinkedList<>();
        for(int i = 0 ; i < nums.length - 2; i++){
            if (nums[i] > 0) { //!!!! nice to have
                return res;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {  // !!!!Skip duplicates for 'i'
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    List<Integer> temp = new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right]));
                    res.add(temp);
                    //!!! Skip duplicates for left
                    //while(right > left) if(nums[left] == nums[left+1])left++; !!!! this will cause time limit exceeded error
                    while(right > left && nums[left] == nums[left+1])left++;
                    // !!!!Skip duplicates for right
                    while(right > left && nums[right] == nums[right-1])right--;
                    left++;
                    right--;
                }else if(sum > 0){
                    right--;
                }else{
                    left++;
                }
            }

        }
        return res;

    }
}

✨

hashMap is hard to get bug free

two pinters is the best solutions for this problem.

!!!

while(left < right && nums[left] == nums[left + 1]) left++;

while(right > left) if(nums[left] == nums[left+1]) left++;

the above two versions of the while loop are functionally equivalent , but in leetcode the second one will cause time limit exceed. 所以以后while后面的if statement最好都一起加进while的条件语句语句

18. 4Sum

Medium

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

1
2
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        //if(nums[0] > target ) return res;
        //cant have this cause like [-3,-2,-1] -5
        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++){ // here should start from i+1 not 0. its easy to have a typo like this
                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){
                        List<Integer> temp = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left],nums[right]));
                        res.add(temp);
                        while(left < right && nums[left] == nums[left+1]) left++;
                        while(left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }else if(nums[i] + nums[j] + nums[left] + nums[right] < target){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
        }
        return res;
    }
}