LeetCode Day5 HashTable
Tags: leetcode, java, algorithms
Published: 2024-06-11 15:49:32

## LeetCode 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:

Input: s = "anagram", t = "nagaram"
Output: true
Example 2:

Input: s = "rat", t = "car"
Output: false

[Original Page](https://leetcode.com/problems/valid-anagram/)

It is not a hard question we can use the HashMap to figure it out.
```
        Map<Character,Integer> sMap = new HashMap<Character,Integer>();
        Map<Character,Integer> tMap = new HashMap<Character,Integer>();
        for(int i=0;i<s.length(); i++){
            Character c = s.charAt(i);
            if(sMap.containsKey(c)){
                sMap.replace(c,sMap.get(c)+1);
            }else{
                sMap.put(c,1);
            }
        }

        for(int i=0;i<t.length(); i++){
            Character c = t.charAt(i);
            if(tMap.containsKey(c)){
                tMap.replace(c,tMap.get(c)+1);
            }else{
                tMap.put(c,1);
            }
        }

        Set<Character> keySet = sMap.keySet();

        for (Character c: keySet){
            if ( !sMap.get(c).equals(tMap.get(c))) {
                return false;
            }
        }



        return s.length() == t.length();
    }
```

But the above method has some defects, even though it is an O(n)method but contains too many redundant codes e.g. we even do not need 2 HashMap we can solve it by using only one hashmap.





## LeetCode 349. Intersection of Two Arrays

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.
[Original Page](https://leetcode.com/problems/intersection-of-two-arrays/description/)
 

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.
 

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000



```
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] selfHash = new int[1001];
        for(int i: nums1){
            selfHash[i] ++;
        }

        for(int i: nums2){
            if(selfHash[i]>0){
                selfHash[i] = -1;
            }
        }
        int size = 0;

        for(int i=0; i<1001; i++){
            if(selfHash[i]<0){
                size++;
            }
        } 
        if(size == 0){
            return new int[0];
        }
        int[] output = new int[size];
        int index = 0;
        for(int i=0; i<1001; i++){
            if(selfHash[i]<0){
                output[index++] = i;
            }
        }

        return output;       
    }
```
Similarly, I also wrote some useless codes, and I think it is not a good idea to use a self-build hashmap (based on the normal array)

It may waste resources because of an un-extensible array, which pushes me to build 1001 sized array(the question said the element will be from 0 to 1000) even though the test case only contains 3 numbers in each input array, we need to build 1001 sized one  

Fortunately, 1000 is not large enough, if the size is 10000000, we can use Set it will be more efficient.

```
public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i : nums1){
            set.add(i);
        }
        Set<Integer> output = new HashSet<Integer>();
        for(int i: nums2){
            if(!set.isEmpty() && set.contains(i)){
                output.add(i);
            }
        }

        return output.stream().mapToInt(Integer::intValue).toArray();
    }
```

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3mmpvzno68gl1hoig4gf.png)
Both of these code are some, we can use x->x because Java can Autoboxing





---
## LeetCode No.1 Two Sum


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:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
[Original Page](https://leetcode.com/problems/two-sum/description/)

This is not a difficult question

```
    public int[] twoSum(int[] nums, int target) {
        int[] result = {-1,-1};
        for(int i=0;i<nums.length;i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[j]+ nums[i] == target){
                    result[0] = j;
                    result[1] = i;
                    return result;
                }
            }
        }
        return result;
    }
```



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