查找表

349. 两个数组的交集

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] more = nums1.length > nums2.length ? nums1 : nums2;
        int[] less = nums1.length > nums2.length ? nums2 : nums1;

        Set<Integer> set = new HashSet<>();
        for (int item : more) {
            set.add(item);
        }

        Set<Integer> result = new HashSet<>();
        for (int item : less) {
            if (set.contains(item)) {
                result.add(item);
            }
        }

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

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

350. 两个数组的交集II

class Solution {
    // 如果数组有序，可以用双指针解题
    public int[] intersect(int[] nums1, int[] nums2) {
        int[] more = nums1.length > nums2.length ? nums1 : nums2;
        int[] less = nums1.length > nums2.length ? nums2 : nums1;

        Map<Integer, Integer> map = new HashMap<>();
        for (int item : more) {
            map.put(item, map.getOrDefault(item, 0) + 1);
        }

        List<Integer> result = new ArrayList<>();
        for (int item : less) {
            if (map.containsKey(item) && map.get(item) > 0) {
                result.add(item);
                map.put(item, map.get(item) - 1);
            }
        }

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

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

242. 有效的字母异位词

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] map = new int[26];
        for (int i = 0; i < s.length(); i++) {
            map[s.codePointAt(i) - 97]++;
            map[t.codePointAt(i) - 97]--;
        }

        for (int item : map) {
            if (item != 0) {
                return false;
            }
        }

        return true;
    }
}

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

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
	  Map<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            int ano = target - nums[i];
            if(map.containsKey(ano)){
                int idx = map.get(ano);
				return new int[]{idx, i};
			}
            map.put(nums[i], i);
        }
        return null;
    }
}

https://leetcode.cn/problems/two-sum

454. 四数相加II

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> sumCount = new HashMap<>();
        for (int e1 : nums1) {
            for (int e2 : nums2) {
                sumCount.merge(e1 + e2, 1, Integer::sum);
            }
        }

        int count = 0;
        for (int e3 : nums3) {
            for (int e4 : nums4) {
                int sum = e3 + e4;
                if (sumCount.containsKey(-sum)) {
                    count += sumCount.get(-sum);
                }
            }
        }

        return count;
    }
}

https://leetcode.cn/problems/4sum-ii

447. 回旋镖的数量

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int result = 0;

        Map<Integer, Integer> distCount = new HashMap<>();
        for (int i = 0; i < points.length; i++) {
            distCount.clear();
            for (int j = 0; j < points.length; j++) {
                if (i != j) {
                    distCount.merge(distSquare(points[i], points[j]), 1, Integer::sum);
                }
            }
            for (Integer count : distCount.values()) {
                result += count * (count - 1);
            }
        }

        return result;
    }

    private Integer distSquare(int[] p1, int[] p2) {
        return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
    }
}

https://leetcode.cn/problems/number-of-boomerangs

219. 存在重复元素II

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k == 0) {
            return false;
        }
        Set<Integer> window = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (!window.add(nums[i])) {
                return true;
            }
            if (window.size() > k) {
                window.remove(nums[i - k]);
            }
        }
        return false;
    }
}

https://leetcode.cn/problems/contains-duplicate-ii

220. 存在重复元素III

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Integer> ts = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            int current = nums[i];
            Integer ceil = ts.ceiling(current);
            Integer floor = ts.floor(current);
            if ((ceil != null && ceil - current <= valueDiff) 
            || (floor != null && current - floor <= valueDiff)) {
                return true;
            }
            ts.add(current);
            if (i >= indexDiff) {
                ts.remove(nums[i - indexDiff]);
            }
        }
        return false;
    }
}

https://leetcode.cn/problems/contains-duplicate-iii