＜冲刺大厂之算法刷题＞Hash表（二）

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

//方法一:使用unordered_map解决.  原因:因为同一个数存在多个,可以使用键值对来进行存储,结果不要求顺序.
//时间复杂度O(N)  空间复杂度O(N)
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
  vector<int> result;
  unordered_map<int,int> nums1_map;
  for(int i = 0; i < nums1.size(); i++) { //初始化nums1_map
    nums1_map[nums1[i]]++;
  }
  //遍历nums2,将重复的元素加入结果集.
  for(int i = 0; i < nums2.size(); i++) {
    if(nums1_map.find(nums2[i])!=nums1_map.end()) {
      nums1_map[nums2[i]]--;
      result.push_back(nums2[i]);//元素放入结果集
      if(nums1_map[nums2[i]]==0) { //如果已经减到了0,则移除
        nums1_map.erase(nums2[i]);
      }
    }
  }
  return result;
}

输入：n = 19
输出：true

输入：n = 2
输出：false

#include<bits/stdc++.h>
using namespace std;
int getSum(int x){//将数替换成数字的平方和 
  int sum = 0;
  while(x){
    sum+=(x%10)*(x%10);
    x /= 10;
  }
  return sum;
}
//由于只需要存这个元素在集合中是否存在,而且不需要重复,所以我们使用unordered_set 
unordered_set<int> set;
bool isHappy(int n) {
  int res = getSum(n);
  while(res!=1){
    if(set.find(res)!=set.end()){
      return false;
    }else{
      set.insert(res);
    }
    res = getSum(res);
  }
  return true;
}

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

输入：nums = [3,2,4], target = 6
输出：[1,2]

输入：nums = [3,3], target = 6
输出：[0,1]

//方法一:暴力法 
vector<int> twoSum(vector<int>& nums, int target) {
  for(int i = 0;i < nums.size();i++) {
    for(int j = i+1;j < nums.size();j++){
      return {i,j};
    }
  }
  return {};
}

vector<int> twoSum(vector<int>& nums, int target) {
  unordered_map<int,int> M;//存放元素以及对应的下标
  for(int i = 0; i < nums.size(); i++) {
    unordered_map<int,int>::iterator iter = M.find(target-nums[i]);//查找其和为target的另外 一个元素是否存在
    if(iter!=M.end()) {
      return {i,iter->second};
    }
    M.insert(pair<int,int>(nums[i],i));//如果没有,则将当前元素插进来.
  }
  return {};//写这个只是为了编译通过,实际运行根本不会走这一步..
}

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

输入：nums = []
输出：[]

输入：nums = [0]
输出：[]

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
  int L,R,sum;
  vector<vector<int>> res;
  if(nums.size()<3) {
    return {} ;
  }
  //进行排序
  sort(nums.begin(),nums.end()) ;
  //如果第一个元素就>0,那么后面的元素一定 > 0
  if(nums[0]>0) {
    return {};
  }
  //遍历元素+双指针
  for(int i = 0; i<nums.size(); i++) {
    if(nums[i]>0) {
      return res;
    }
    if(i>0&&nums[i]==nums[i-1]) { //进行去重
      continue;
    }
    L = i+1;
    R = nums.size()-1;
    while(L < R) {//采用双指针法 枚举所有的三元对情况 
      sum = nums[i]+nums[L]+nums[R];
      if(!sum) {
        res.push_back({nums[i],nums[L],nums[R]});
        //进行去重
        while(L + 1<R && nums[L]==nums[L+1]) {
          L++;
        }
        while(R-1 > L && nums[R]==nums[R-1]) {
          R--;
        }
        L++;
        R--;
      } else if(sum > 0) {
        R--;
      } else if(sum < 0) {
        L++;
      }
    }
  }
  return res;
}

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1