关于leetcode上的查找问题 java版
查找问题是老生常谈的问题，我们平常会遇到很多例子。
主要分为两类
- 查找有无
元素a是否出现？主要使用set 集合 - 查找对应关系
元素a出现了几次？主要使用map也就是字典
通常语言标准库内置set和map。容器类
常见操作有四个insert，find，erase，change（map）
接下来由简单的问题引入
leetcode 349号问题TWO SIGMA
题目：
给定两个数组，写一个函数来计算它们的交集。
例子:
给定 num1= [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].
提示:
每个在结果中的元素必定是唯一的。
我们可以不考虑输出结果的顺序。
我个人写的代码
public static void main(String[] args) {
int[] nums1={1,2,2,1};
int[] nums2={2,2};
Set<Integer> set = new HashSet<Integer>();
for(int i=0;i<nums1.length;i++){
for(int m=0;m<nums2.length;m++)
{
if(nums1[i]==nums2[m]){
if(!(set.contains(nums1[i])))
set.add(nums1[i]);
}
}
}
for (Integer m : set) {
System.out.print(m);
}
}
另一种方法，把nums1[]数组插入set，由于set不会有重复元素，所以多次插入也无所谓，然后差不多的方法
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> nums1Set(nums1.begin(),nums1.end());
set<int> resSet;
for(int i =0; i < nums2.size();++i)
if(nums1Set.find(nums2[i]) != nums1Set.end())
resSet.insert(nums2[i]);
return vector<int>(resSet.begin(),resSet.end());
}
};
接下来是map的使用
leetcode350
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
来源：力扣（LeetCode）
这是我的答案，能通过但是效率太低。而且integer转int会出现边界错误，它的测试用例有一个就是-2147483648。所以我把他转化成了string
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<String,Integer> map1=new HashMap<String,Integer>();
Map<String,Integer> map3=new HashMap<String,Integer>();
for(int i=0;i<nums1.length;i++)
{
Integer v = map1.get(String.valueOf(nums1[i]));
map1.put(String.valueOf(nums1[i]), v == null ? 1 : (v + 1));
}
Map<String,Integer> map2=new HashMap<String,Integer>();
for(int i=0;i<nums2.length;i++)
{
Integer v = map2.get(String.valueOf(nums2[i]));
map2.put(String.valueOf(nums2[i]), v == null ? 1 : (v + 1));
}
for (String key1 : map1.keySet()) {
for (String key2 : map2.keySet()) {
if(key1.equals(key2))
{
if(map1.get(key1)>map2.get(key2))
map3.put(key1,map2.get(key2));
else
map3.put(key1,map1.get(key1));
}
}
}
int a=0;
for (String key : map3.keySet()) {
a+=map3.get(key);
}
int[] b=new int[a];
int d=0;
for (String key : map3.keySet()) {
for(int c=0;c<map3.get(key);c++)
{b[d]=Integer.valueOf(key);
d++;
}
}
return b;
}
}
接下来看看其他人的答案.来自于leetcode中本体的讨论区
说一下特点，在下列方法中映射代表使用了map
因为list大小可变，所以先存在list中。然后在nums2数组中查找，这个数如果在nums2多一些，count--就会为0，就停止添加。如果在nums1多一些，那么就会把nums2中所有同一个数添加完
public int[] intersect_3(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>(nums1.length);
// 将 nums1 出现的数值及频次放入映射中
for (int num : nums1) {
Integer count = map.get(num);
if (count == null) {
map.put(num, 1);
} else {
map.put(num, ++count);
}
}
List<Integer> list = new ArrayList<>();
for (int num : nums2) {
// 获取映射中该数值出现的频次
Integer count = map.get(num);
if (count != null && count != 0) {
list.add(num);
// 注意每次匹配后，该数值的频次需要减 1（nums1 和 nums2 匹配的数值的频次要相同）
map.put(num, --count);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
class Solution {
/**
* 使用集合实现
*/
public int[] intersect_1(int[] nums1, int[] nums2) {
List<Integer> list1 = new ArrayList<>();
for (int num : nums1) {
list1.add(num);
}
List<Integer> list2 = new ArrayList<>();
for (int num : nums2) {
if (list1.contains(num)) {
list2.add(num);
// 从 list1 除去已匹配的数值
list1.remove(Integer.valueOf(num));
}
}
int[] res = new int[list2.size()];
int i = 0;
for (int num : list2) {
res[i++] = num;
}
return res;
}
/**
* 使用集合的实现
*/
public int[] intersect_2(int[] nums1, int[] nums2) {
List<Integer> list1 = Arrays.stream(nums1)
.boxed()
.collect(Collectors.toList());
List<Integer> list2 = Arrays.stream(nums2)
.boxed()
.filter(num -> {
if (list1.contains(num)) {
list1.remove(num);
return true;
}
return false;
})
.collect(Collectors.toList());
int[] res = new int[list2.size()];
for (int i = 0; i < list2.size(); i++) {
res[i] = list2.get(i);
}
return res;
}
/**
* 使用映射实现
*/
public int[] intersect_3(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>(nums1.length);
// 将 nums1 出现的数值及频次放入映射中
for (int num : nums1) {
Integer count = map.get(num);
if (count == null) {
map.put(num, 1);
} else {
map.put(num, ++count);
}
}
List<Integer> list = new ArrayList<>();
for (int num : nums2) {
// 获取映射中该数值出现的频次
Integer count = map.get(num);
if (count != null && count != 0) {
list.add(num);
// 注意每次匹配后，该数值的频次需要减 1（nums1 和 nums2 匹配的数值的频次要相同）
map.put(num, --count);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
/**
* 排序预处理
*/
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> list = new ArrayList<>();
for (int i = 0, j = 0; i < nums1.length && j < nums2.length; ) {
if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
list.add(nums1[i]);
i++;
j++;
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
}
接下来是leetcode的1号问题TWO SUM
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
使用查找表。将所有元素放入查找表，之后对于每一个元素a，查找target - a 是否存在。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++) {
if(map.containsKey(target - nums[i])) { //这样做是为了如果是82，数据是[1,41,41,88]这种，map（42,1）会被map（42,2）覆盖掉，导致找不出结果
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return null;
}
}
以上时间复杂度0(N),空间复杂度O（N）
看了2sum，接着看4sum
来自于leetcode的454题 4sum
给定四个包含整数的数组列表 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 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
- (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
来源：力扣（LeetCode）
用普通的查找表示复杂度是n的立方，仍然很复杂。如果是n的平方那么还可以接受
但是还是用查找表思想，A+B+C+D=0可以转换为A+B=-C-D，把A+B的值作为map里的值存进来，然后在 C+D里找有没有相等的
以下是java版实现
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer,Integer> record=new HashMap<Integer,Integer>();
for(int i=0;i<A.length;i++)
for(int j=0;j<B.length;j++)
{
Integer v = record.get(A[i]+B[j]);
record.put(A[i]+B[j],v == null ? 1 : (v + 1));
}
int res=0;
for(int i=0;i<C.length;i++)
for(int j=0;j<D.length;j++)
{
if(record.containsKey(0-C[i]-D[j]))
res+=record.get(0-C[i]-D[j]);
}
return res;
}
对于查找问题，还可以用原来的滑动窗口+查找表来实现
来源于leetcode219号题
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
来源：力扣（LeetCode）
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> record=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++)
{
if(record.containsKey(nums[i]))
return true;
record.put(nums[i],1);
//保持record中最多有k个元素
if(record.size()==k+1)
record.remove(nums[i-k]);
}
return false;
}
}
