一、查找问题通常有2类
1、查找有无 ：元素a是否存在？set；集合
2、查找对应关系（键值对应）：元素a出现了几次？map；字典
给定两个数组，编写一个函数来计算它们的交集
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
import java.util.HashSet;
import java.util.Set;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> record = new HashSet<>();
Set<Integer> result = new HashSet<>();
for (int num : nums1) {
record.add(num);
}
for (int num : nums2) {
if (record.contains(num)) {
result.add(num);
}
}
int[] res = new int[result.size()];
int i = 0;
for (int num : result) {
res[i] = num;
i++;
}
return res;
}
}
给定两个数组，编写一个函数来计算它们的交集。
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
import java.util.*;
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> record = new HashMap<>();
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < nums1.length; i++) {
if (record.containsKey(nums1[i]))
record.put(nums1[i], record.get(nums1[i]) + 1);
else
record.put(nums1[i], 1);
}
for (int j = 0; j < nums2.length; j++) {
if (record.containsKey(nums2[j]) && record.get(nums2[j]) > 0) {
list.add(nums2[j]); //添加到list中
record.put(nums2[j], record.get(nums2[j]) - 1);
}
}
int count = list.size();
int[] aux = new int[count];
for (int i = 0; i < count; i++) {
aux[i] = list.get(i);
}
return aux;
}
}
相关问题242，202，290，205，451
二、一个使用查找表的经典问题
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]
几种思路
import java.util.*;
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> record = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int value = target - nums[i];//只将value前面的元素放入查找表中
if (record.containsKey(value)) {//value前面的某个元素和value相等
return new int[]{record.get(value), i};//找到解
}
record.put(nums[i], i);//如果查找失败就将value也纳入到查找表，
}
throw new IllegalArgumentException("No two sum solution");
}
相关问题，15，18，16
三、灵活选择键值
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。(所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500)
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
import java.util.*;
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
//key,C+D的所有可能性，value是可能性出现的频率
Map<Integer, Integer> record = new HashMap<>();
for (int i = 0; i < C.length; i++) {
for (int j = 0; j < D.length; j++) {
int sum = C[i] + D[j];
if (record.containsKey(sum)) {
record.put(sum, record.get(sum) + 1);
} else {
record.put(C[i] + D[j], 1);
}
}
}
int count = 0;
//记录A，B 任意组合的和的负值，然后在查找表中查找是否有对应的值
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
int res = -(A[i] + B[j]);
if (record.containsKey(res)) {
count += record.get(res);
}
}
}
return count;
}
}
相关问题49
给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。（n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中）
输入:
[[0,0],[1,0],[2,0]]
输出:
2
观察到i是一个枢纽，对于每个点i，遍历其余点到i的距离，O(n^2)
对于每个点i，设计出这样一张查找表，扫描一遍所有的其他点，计算出其他点到i的距离，在查找表中对应的键就是距离的值，对应的值就是有多少个这样的点
查找表
import java.util.*;
class Solution {
public int numberOfBoomerangs(int[][] points) {
int res = 0;
for (int i = 0; i < points.length; i++) {
Map<Integer, Integer> record = new HashMap<>();//对于每个点i，都设置一个查找表，
for (int j = 0; j < points.length; j++) {
if (j != i) {
//找到了一个和i不同的点，计算距离
int distance = (points[i][0] - points[j][0]) * (points[i][0] - points[j][0]) +
(points[i][1] - points[j][1]) * (points[i][1] - points[j][1]);
res += record.getOrDefault(distance, 0) * 2;
record.put(distance, record.getOrDefault(distance, 0) + 1);
}
}
}
return res;
}
}
相关问题149
四、查找表和滑动窗口
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
输入: nums = [1,2,3,1], k = 3
输出: true
滑动窗口思路，i和j在l到l+k区间内，这个区间有k+1个元素，在一个连续的有有k+1个元素的区间中，如果能找到2个元素他们的值相等，就能保证这两个元素的索引的差也一定是小于等于k的
滑动窗口
l+k区间
import java.util.*;
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> record = new HashSet<>();
//在散列表中搜索当前元素，如果找到了就返回 true。
//在散列表中插入当前元素。
//如果当前散列表的大小超过了 kk， 删除散列表中最旧的元素。
for (int i = 0; i < nums.length; i++) {
if (record.contains(nums[i])) {
return true;
}
record.add(nums[i]);
if (record.size() == k + 1) {
record.remove(nums[i - k]);
}
}
return false;
}
}
相关问题217
五、 二分搜索树底层实现的顺序性
给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
import java.util.*;
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Integer> record = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
//找到当前元素的后继
Integer s = record.ceiling(nums[i]);
if (s != null && s <= nums[i] + t) {
return true;
}
//找到当前元素的前身
Integer g = record.floor(nums[i]);
if (g != null && nums[i] <= g + t) {
return true;
}
record.add(nums[i]);
if (record.size() == k + 1) {
record.remove(nums[i - k]);
}
}
return false;
}
}