一、数组作为哈希表

242. 有效的字母异位词

https://leetcode-cn.com/problems/valid-anagram/

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

383. 赎金信

https://leetcode-cn.com/problems/ransom-note/

	public boolean canConstruct(String ransomNote, String magazine) {
		
		int[] record = new int[26];
		for(char c : magazine.toCharArray()){
			record[c - 'a']++;
		}
		
		for(char c : ransomNote.toCharArray()){
			record[c - 'a']--;
			if(record[c - 'a'] < 0) return false;
		}
		
		return true;
	}

49. 字母异位词分组（未完成）

https://leetcode-cn.com/problems/group-anagrams/

438. 找到字符串中所有字母异位词

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

	public List<Integer> findAnagrams(String s, String p) {
		int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }
        
        List<Integer> ans = new ArrayList<Integer>();

        int[] pCount = new int[26];
        int[] sCount = new int[26];
        
        //先把第一组数比较一下
        for(int i=0; i<pLen; i++){
        	pCount[p.charAt(i)-'a']++;
        	sCount[s.charAt(i)-'a']++;
        }
        //第一组数一样就放进ans
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }
        //然后每次后面加一个，前面减一个
        for (int i = 0; i < sLen - pLen; ++i) {
        	sCount[s.charAt(i)-'a']--;
        	sCount[s.charAt(i+pLen)-'a']++;
        	
        	if(Arrays.equals(sCount, pCount)){
        		ans.add(i+1);//注意这里是i加1！虽然i从0开始，但是0位置上已经判断过了
        	}
        }          
        return ans;
	}

二、set作为哈希表

349. 两个数组的交集

https://leetcode-cn.com/problems/intersection-of-two-arrays/

两个哈希
排序

	/**
	 * 执行用时：2 ms, 在所有 Java 提交中击败了93.30%的用户
	 * 内存消耗：41 MB, 在所有 Java 提交中击败了42.74%的用户
	 */
	public int[] intersection2(int[] nums1, int[] nums2) {
		Set<Integer> set1 = new HashSet<>();
		Set<Integer> set2 = new HashSet<>();
		//遍历数组1，把数加紧哈希1
		for(int i : nums1){
			set1.add(i);
		}
		//遍历数组2，数组里里有，加进哈希2
		for(int i : nums2){
			if(set1.contains(i)){
				set2.add(i);
			}
		}
		//把哈希2转化成数组
		int[] ans = new int[set2.size()];
		int index = 0;
		for(int i: set2){
			ans[index] = i;
			index++;
		}
		return ans;
	}
	/**
	 * 执行用时：2 ms, 在所有 Java 提交中击败了93.30%的用户
	 * 内存消耗：41.3 MB, 在所有 Java 提交中击败了30.39%的用户
	 */
	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){
        		index2++;
        	}else{
        		index1++;
        	}       	
        }       
        return Arrays.copyOfRange(intersection, 0, index);
	}

三、map作为哈希表

350. 两个数组的交集 II

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
和上题方法类似

哈希
排序双指针

	/**
	 * 执行用时：2 ms, 在所有 Java 提交中击败了85.62%的用户
	 * 内存消耗：41.5 MB, 在所有 Java 提交中击败了18.33%的用户
	 */
	public int[] intersect2(int[] nums1, int[] nums2) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		//1.遍历数组1把哈希映射放进去
		for(int num:nums1){
			int count = map.getOrDefault(num, 0) + 1;
			map.put(num, count);
		}
		//2.创造数组ans，最终答案不会比ans长
		int[] ans = new int[nums1.length];
        int index = 0;
		//3.遍历数组2中每一个数，哈希中不存在或为0就不放入ans中
        for(int num:nums2){
        	int count = map.getOrDefault(num, 0);//当前这个数在哈希里的值，没有就是0
        	if(count > 0){//大于0才放
        		ans[index++] = num;
        		count--;//减去放的这个
        		if(count == 0){//如果减完这一个就没了，连key一起删了
        			map.remove(num);
        		}else{//如果减完还有，再放回去
        			map.put(num, count);
        		}
        	}
        }
        return Arrays.copyOfRange(ans, 0, index);
	}
	
	
	
	/**
	 * 执行用时：2 ms, 在所有 Java 提交中击败了85.62%的用户
	 * 内存消耗：41.7 MB, 在所有 Java 提交中击败了6.10%的用户
	 */
	public int[] intersect(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){
        		intersection[index++] = num1;
                index1++;
                index2++;
        	}else if(num1 > num2){
        		index2++;
        	}else{
        		index1++;
        	}       	
        }       
        return Arrays.copyOfRange(intersection, 0, index);
	}

454. 四数相加 II

https://leetcode-cn.com/problems/4sum-ii/
分成两拨，有点像两数之和

	public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
		int ans = 0;
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		//把1和2的和以及个数存一下
		for(int i : nums1){
			for(int j :nums2){
				int sum12 = i+j;
				int count1 = map.getOrDefault(sum12, 0) + 1;
				map.put(sum12, count1);
			}
		}
		//遍历3和4的和看有没有合适的
		for(int i : nums3){
			for(int j : nums4){
				int sum34 = i+j;
				int neednum = 0 - sum34;
				//如果存在所需要的这个数
				if(map.containsKey(neednum)){
					ans+=map.get(neednum);
				}
			}
		}		
		return ans;
	}

四、像用哈希但是其实哈希不合适

15. 三数之和

这题不适合用哈希。

两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。

把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。

去重的过程不好处理，有很多小细节，如果在面试中很难想到位。

排序+双指针

	public List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        
        for(int i=0; i<nums.length; i++){
        	if (nums[i] > 0) return ans;//如果一开始就大于0，后面肯定没有正确答案
        	if (i > 0 && nums[i] == nums[i - 1]) continue;//如果和刚才一样，没必要重算
        	
        	int l = i+1;
        	int r = nums.length-1;
        	while(l<r){
        		int tosum = nums[i] + nums[l] + nums[r];
        		if(tosum == 0){//如果当前三个数和为0
        			List<Integer> newans = new ArrayList<Integer>();
        			newans.add(nums[i]);
        			newans.add(nums[l]);
        			newans.add(nums[r]);
        			ans.add(newans);
        			//直到左右没有重复的数字为止
        			while (r > l && nums[r] == nums[r - 1]) r--;
                    while (r > l && nums[l] == nums[l + 1]) l++;
                    //因为当前已经满足和为0了，所以必须左右同时减，只有一边动的话肯定不满足
                    r--; 
                    l++;
        		}else if(tosum < 0){
        			l++;
        		}else{
        			r--;
        		}
        	}       	
        }       
        return ans;
	}

18. 四数之和

https://leetcode-cn.com/problems/4sum/
和三数之和一个逻辑，多一层for循环

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