Skip to content

Latest commit

 

History

History
1029 lines (877 loc) · 25.4 KB

6_哈希.md

File metadata and controls

1029 lines (877 loc) · 25.4 KB
Raw

查找表相关问题

一、set 的使用

*1、两个数组的交集(349)

349. 两个数组的交集

//思路：
// 要求结果只出现一次，马上要想到set(该集合不允许重复元素)，
// 最终求两个数组的交集， 就是求这两个数组相应的set的交集。
public int[] intersection(int[] nums1, int[] nums2) {
  Set<Integer> record = new HashSet<>();
  for(int num : nums1){
    record.add(num);
  }

  Set<Integer> resultSet = new HashSet<>();
  for(int num : nums2){
    if(record.contains(num)){
      resultSet.add(num);
    }
  }

  int[] res = new int[resultSet.size()];
  int index = 0;
  for(int num : resultSet){
    res[index++] = num;
  }
  return res;
}

@Test
public void test(){
  //int[] nums1 = {1,2,2,1}, nums2 = {2,2};
  int[] nums1 = {4,9,5}, nums2 = {9,4,9,8,4};
  int[] res = intersection(nums1,nums2);
  for(int num : res){
    System.out.println(num);
  }
}

*2、模拟行走机器人(874)

874. 模拟行走机器人

// 思路:
// 1、机器人能向左、向右和向前移动，说明机器人能够向上、下、左、右四个方向移动，那就准备一个二维数组来表示这四个方向：
// int[][] d={{0,1},{1,0},{0,-1},{-1,0}};
// 2、准备一个set存储障碍物的下标(这里使用字符串表示)，方便判断机器人是否会遇到该障碍物
// 3、如果遇到障碍物，机器人会中断原来的路径，此时执行下一个指令，继续行走
// 注意：
// 由于要求得到最大值，机器人最后停下的位置不一定能获取最大值，所以要准备变量记录最大值。
public int robotSim(int[] commands, int[][] obstacles) {

  //存储障碍物的下标(这里使用字符串表示)，方便判断机器人是否会遇到该障碍物
  Set<String> obstaclesSet = new HashSet<>();

  if(obstacles.length > 0){
    for(int[] o : obstacles){
      obstaclesSet.add(o[0]+","+o[1]);
    }
  }

  int x=0,y=0; //机器人的位置为(x,y)
  int res=0;
  int direction = 0; // 机器人默认是向上走的，对应 d[0]

  for(int command : commands){ // command 可能的取值-2,-1,任意正整数
    if(command == -2){ //向左转
      direction = (direction+3)%4;
    }else if(command == -1){ //向右转
      direction = (direction+1)%4;
    }else{
      while(command-- > 0){ //机器人此时最多可走 command 步
        int newX = x+d[direction][0];
        int newY = y+d[direction][1];
        //沿着 direction 方向走 1 步,得到的新坐标 (newX,newY)
        if(obstaclesSet.contains(newX+","+newY)){
          break;
        }
        x = newX;
        y = newY;
      }

    }
    res = Math.max(res,x*x+y*y);
  }

  return res;
}

private int[][] d={ // 注意坐标和二维数组的区别
  {0,1}, //向上
  {1,0}, //向右
  {0,-1}, //向下
  {-1,0}  //向左
};


@Test
public void test(){
  int[] commands = {4,-1,3};
  int[][] obstacles = {};
  //int[] commands = {4,-1,4,-2,4};
  //int[][] obstacles = {{2,4}};
  System.out.println(robotSim(commands,obstacles));
}

3、快乐数(202)

202. 快乐数

public boolean isHappy(int n) {
  //set 中存的就是根据 n 产生的中间数
  Set<Integer> set = new HashSet<>();
  while(n!=1){
    if(set.contains(n)){ // set 中存在 n ，就会陷入循环中
      return false;
    }else{
      set.add(n);
      n = tmpNumber(n);
    }
  }
  // n == 1 此时就会退出循环，说明 n 是快乐数
  return true;
}

//根据 n 产生的临时中间数
// n = 19,此时中间数就是 1^2+9^2=82
private int tmpNumber(int n){
  int tmp = 0;
  while(n>0){
    tmp = (n%10)*(n%10);
    n /=10;
  }
  return tmp;
}

@Test
public void test(){
  int n=19;
  System.out.println(isHappy(n));
}

二、set 和滑动窗口

1、存在重复元素（217）

public boolean containsDuplicate(int[] nums) {
  Set<Integer> set = new HashSet<>();

  for(int num : nums){
    if(set.contains(num)){
      return true;
    }
    set.add(num);
  }
  return false;
}

@Test
public void test(){
  //int[] nums={1,2,3,1};
  //int[] nums={1,2,3,4};
  int[] nums={1,1,1,3,3,4,3,2,4,2};
  System.out.println(containsDuplicate(nums));
}

*2、存在重复元素II（219）

//思路一：
//存在索引 i 和 j，使得 nums[i]==nums[j] 并且 i 和 j 的差的最大绝对值为 k。
//也就是说，只要 i 和 j 差的最小绝对值 <= k 即可。
public boolean containsNearbyDuplicate(int[] nums, int k) {
  HashMap<Integer,Integer> map = new HashMap<>();
  int abs = Integer.MAX_VALUE;
  for(int i=0;i<nums.length;i++){
    int num = nums[i];
    if(map.containsKey(num)){
      abs = Math.min(abs,Math.abs(i-map.get(num)));
    }
    map.put(num,i);
  }
  if(abs<=k){
    return true;
  }
  return false;
}
//思路二：
//滑动窗口和查找表的综合使用，维持一个长度最长为 k 的滑动窗口，
//在该窗口查找是否有两个相等的元素。
public boolean containsNearbyDuplicate(int[] nums, int k) {
  if(k<1){
    return false;
  }
  Set<Integer> set = new HashSet<>();
  for(int i=0;i<nums.length;i++){
    int num = nums[i];
    if(set.contains(num)){ // num 是滑动窗口中元素
      return true;
    }
    set.add(num);
    if(set.size()==k+1){ //滑动窗口过长
      //假设要删除的元素下标为 x，则有 i-x+1=k+1 --> x=k-i;
      set.remove(nums[i-k]);
    }
  }
  return false;
}

@Test
public void test(){
  int[] nums={1,2,3,1};
  int k = 3;
  //int[] nums={1,0,1,1};
  //int k=1;
  //int[] nums={1,2,3,1,2,3};
  //int k=2;
  System.out.println(containsNearbyDuplicate(nums,k));
}

*3、存在重复元素 III（220）

220. 存在重复元素 III

//思路：类比 219 题
//|nums[j]-nums[i]|<=t，则有 nums[i]-t <= nums[j] <= nums[i]+t;
//也就是说在长度不超过 k 的滑动窗口中存在元素在 nums[i] 和 nums[j]，
//使得 nums[i]-t <= nums[j] <= nums[i]+t。
//nums[i]+t 有可能很大，所以使用 Long 类型。
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  if (k < 1 || t < 0){ //注意：k和t是否合理
    return false;
  }
  //注意:set 的选择，set 必须是有序的，方面后面进行查找（这里就是 BST）
  SortedSet<Long> set=new TreeSet<>();
  for(int i=0;i<nums.length;i++){
    int num = nums[i];
    // num + t有可能很大，十一
    Set<Long> subSet = set.subSet((long)num-t,(long)num+t+1);//注意：左闭右开
    if(!subSet.isEmpty()){ //不为空，说明存在 nums[j]
      return true;
    }
    set.add((long)num);
    if(set.size()==k+1){
      set.remove((long)nums[i-k]);
    }
  }
  return false;
}

@Test
public void test(){
  //int[] nums = {1,2,3,1};
  //int k = 3, t = 0;

  //int[] nums={1,0,1,1};
  //int k = 1,t =2;

  int[] nums={1,5,9,1,5,9};
  int k =2,t=3;

  System.out.println(containsNearbyAlmostDuplicate(nums,k,t));
}

三、map 的使用

*1、两个数组的交集 II(350)

350. 两个数组的交集 II

//TODO:十分经典的问题
public int[] intersect(int[] nums1, int[] nums2) {
  //统计 nums 1 中元素出现次数
  Map<Integer,Integer> record = new HashMap<>();
  for(int num : nums1){
    int freq = record.getOrDefault(num,0);
    record.put(num,++freq);
  }

  List<Integer> resList = new ArrayList<>();

  for(int num : nums2){
    int freq = record.getOrDefault(num,0);
    if(freq>0){
      resList.add(num);
      record.put(num,--freq);
    }
  }

  int[] res = new int[resList.size()];
  for(int i=0;i<resList.size();i++){
    res[i] = resList.get(i);
  }

  return res;
}

@Test
public void test(){
  //int[] nums1 = {1,2,2,1};
  //int[] nums2 = {2,2};

  int[] nums1 = {4,9,5};
  int[] nums2 = {9,4,9,8,4};
  int[] res = intersect(nums1,nums2);
  for(int num : res){
    System.out.println(num);
  }
}

*2、有效的字母异位词(242)

242. 有效的字母异位词

//思路：与 350 题类似
//1、先统计 s 中字符出现次数，然后再与 t 中出现的字符进行对比
//2、由于只包含小写字母，所以可以使用数组来进行统计
    
//写法一：
public boolean isAnagram(String s, String t) {
  if(s.length() != t.length()){
    return false;
  }

  int[] record = new int[26];

  //统计 s 中字符出现的次数
  for(int i=0;i<s.length();i++){
    char c = s.charAt(i);
    record[c-'a']++;
  }

  for(int i=0;i<t.length();i++){
    char c = t.charAt(i);
    int freq = record[c -'a'];
    if(freq > 0){
      record[c-'a']--;
    }
  }

  for(int i=0;i<record.length;i++){
    if(record[i]>0){
      return false;
    }
  }
  return true;
}

@Test
public void test(){
  //String s = "anagram", t = "nagaram";
  String s = "rat", t = "car";
  System.out.println(isAnagram(s,t));
}
//写法二：是对写法一的优化
public boolean isAnagram(String s, String t) {
  if(s.length() != t.length()){
    return false;
  }

  int[] record = new int[26];

  char[] sArray = s.toCharArray();
  char[] tArray = t.toCharArray();

  for(char c :sArray){
    record[c-'a']++;
  }

  for(char c : tArray){
    record[c-'a']--;
  }

  for(int i=0;i<record.length;i++){
    if(record[i]>0){
      return false;
    }
  }
  return true;
}

@Test
public void test(){
  String s = "anagram", t = "nagaram";
  //String s = "rat", t = "car";
  System.out.println(isAnagram(s,t));
}
//使用 map 对字符进行统计
public boolean isAnagram(String s, String t) {
  if(s.length() != t.length()){
    return false;
  }

  Map<Character,Integer> record = new HashMap<>();

  char[] sArray = s.toCharArray();
  char[] tArray = t.toCharArray();

  for(char c :sArray){
    int freq = record.getOrDefault(c,0);
    record.put(c,++freq);
  }

  for(char c : tArray){
    int freq = record.getOrDefault(c,0);
    record.put(c,--freq);
  }

  for(Character c : record.keySet()){
    int freq = record.getOrDefault(c,0);
    if(freq>0){
      return false;
    }
  }
  return true;
}

@Test
public void test(){
  //String s = "anagram", t = "nagaram";
  String s = "rat", t = "car";
  System.out.println(isAnagram(s,t));
}

*3、单词规律（290）

290. 单词规律

public boolean wordPattern(String pattern, String str) {
  if(pattern==null){
    return false;
  }

  String[] strs = str.trim().split(" ");
  char[] chs = pattern.toCharArray();


  if(strs.length != chs.length){
    return false;
  }

  //存储 pattern 中字符和 str 中字符串的映射关系
  Map<Character,String> map = new HashMap<>();

  for(int i=0;i<chs.length;i++){
    Character c=chs[i];
    String s = strs[i];
    if(map.containsKey(c)){
      String old = map.get(c);
      if(!old.equals(s)){
        return false;
      }
    }else{
      // 比如 a->dog,则 b->dog是不被允许的,
      // 所以不仅要判断 key是否在 map 中，也要判断 value 是否在 map 中
      if(map.containsValue(s)){
        return false;
      }
      map.put(c,s);
    }
  }
  return true;
}

@Test
public void test(){
  //String pattern = "abba", str = "dog cat cat dog";
  //String pattern = "abba", str = "dog cat cat fish";
  //String pattern = "aaaa", str = "dog cat cat dog";
  String pattern = "abba", str = "dog dog dog dog";
  System.out.println(wordPattern(pattern,str));
}

4、根据字符出现频率排序（451）

451. 根据字符出现频率排序

//思路：
//1、题目要求根据出现的次数，进行降序排列。
//2、这里我们使用字符出现的次数作为键值，必然会有出现次数相同的字符，将这些字符作为集合构成键值
//3、使用TreeMap，按照键出现次数进行升序排列，最终得到结果。
public String frequencySort(String s) {

  char[] chs = s.toCharArray();
  //统计 s 中字符出现的次数
  int[] freq = new int[256];
  for(int i=0;i<chs.length;i++){
    freq[chs[i]]++;
  }

  //键为字符出现的次数，值为出现该次数的键（不只一个，所以使用链表）
  Map<Integer,List<Character>> records = new TreeMap<>(
    new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        int num = o2-o1; // 根据字符出现次数进行降序排序
        return num;
      }
    });

  for(int i=0;i<256;i++){
    int frequency = freq[i];
    if(frequency==0){
      continue;
    }
    if(!records.containsKey(frequency)){
      //TODO：map中不包含该frequency，则创建新集合，用来存储元素
      records.put(frequency,new ArrayList<>());
    }
    records.get(frequency).add((char) i);
  }

  // records 中的字符此时已经按照出现频率进行降序排好
  StringBuilder builder = new StringBuilder();
  for(Integer frequency:records.keySet()){
    List<Character> list = records.get(frequency);
    for(Character c : list){
      for(int i=0;i<frequency;i++){
        builder.append(c);
      }
    }
  }

  return builder.toString();
}

@Test
public void test(){
  //String s = "tree";
  //String s="cccaaa";
  String s="Aabb";
  System.out.println(frequencySort(s));
}

四、使用查找表的经典问题

*1、两数之和(1)

1. 两数之和

//思路：查找表问题。
//将所有元素加入查找表，之后对于每一个元素a,查找target-a是否存在。
//这里要用到HashMap<Integer,Integer>,键存储的是该元素的值，值存储的是该元素的下标，
//注意：有可能存在相同的元素，则键值相同，会发生值覆盖问题。
//解决：遍历nums的数组，下标在[0,i)元素已经在查找表中，判断 target-nums[i]，是否在查找表。
//如果存在，返回结果
//如果不存在，将 nums[i] 加入查找表中
public int[] twoSum(int[] nums, int target) {
  if(nums.length<=1){
    return new int[]{};
  }

  //<k,v> k 元素， v 该元素下标
  Map<Integer,Integer> records = new HashMap<>();
  for(int i=0;i<nums.length;i++){
    int num = target-nums[i];
    if(records.containsKey(num)){ //判断 records 之前是否存在该元素
      return new int[]{i,records.get(num)};
    }
    records.put(nums[i],i);
  }
  return new int[]{};
}

@Test
public void test(){
  int[] nums = {2, 7, 11, 15};
  int target = 9;
  int[] res = twoSum(nums,target);
  for(int num : res){
    System.out.println(num);
  }
}
//问题 1 的变形：
//给定一个包含 n 个整数的数组 nums 和一个目标值 target，
//判断 nums 中是否存在四个元素 a，b，使得 a + b 的值与 target 相等？
//找出所有满足条件且不重复的四元组。
public List<List<Integer>> twoSum(int[] nums,int target) {
  List<List<Integer>> res = new ArrayList<>();

  Arrays.sort(nums);
  int l=0;
  int r=nums.length-1;
  while(l<r){
    if(nums[l]+nums[r]==target){
      res.add(Arrays.asList(nums[l],nums[r]));
      while(l<r && nums[l]==nums[l+1]){
        l++;
      }
      while(l<r && nums[r]==nums[r-1]){
        r--;
      }
      l++;
      r--;
    }else if(nums[l]+nums[r]<target){
      l++;
    }else{
      assert nums[l]+nums[r]>target;
      r--;
    }
  }
  return res;
}

@Test
public void test(){
  int[] nums = {2, 7, 11, 15};
  int target = 9;
  System.out.println(twoSum(nums,target));
}

*2、三数之和(15)

15. 三数之和

//思路：
//a+b+c=0，则有 a+b=-c
//使用对撞指针方式，在数组组查找两个元素 a、b 使得 a+b = -c
public List<List<Integer>> threeSum(int[] nums) {
  List<List<Integer>> res = new ArrayList<>();

  //使用对撞指针方式就是需要数组是有序的
  Arrays.sort(nums);

  //i 指向当前元素 nums[i],
  //在[i+1,n-1]范围内至少要有 2 个元素 a、b，使得 a+b+nums[i] = 0
  //随意 i <= (n-3)
  for(int i=0;i<nums.length-2;i++){
    if(i>0 && nums[i-1]==nums[i]){
      continue;
    }
    int l=i+1;
    int r=nums.length-1;
    int target = -nums[i];
    while(l<r){ //[l,r] 范围内只要要有 2 个元素，所以 l != r
      if(nums[l]+nums[r]==target){
        res.add(Arrays.asList(nums[l],nums[r],nums[i]));
        while(l<r && nums[l]==nums[l+1]) {
          l++;
        }
        while(l<r && nums[r]==nums[r-1]){
          r--;
        }
        l++;
        r--;
      }else if(nums[l]+nums[r]>target){
        r--;
      }else{
        assert (nums[l]+nums[r]<target);
        l++;
      }
    }
  }

  return res;
}

@Test
public void test(){
  int[] nums = {-1, 0, 1, 2, -1, -4};
  System.out.println(threeSum(nums));
}

3、四数之和（18）

18. 四数之和

//思路：
//其实与 15 题思路类似。a + b + c + d == target
//其实就是 a+b+c = target-d 转化为 3 数之和问题。
public List<List<Integer>> fourSum(int[] nums, int target) {
  List<List<Integer>> res = new ArrayList<>();

  Arrays.sort(nums); //转化为 3 数之和问题就可以使用对撞指针

  //nums[i]对应的在[i+1,n-1] 中查找 3 个元素，则 i<= n-4
  for(int i=0;i<nums.length-3;i++){
    if(i>0 && nums[i-1]==nums[i]){ //去除重复元素
      continue;
    }
    //[j+1,n-1] 中查找 2 个元素，则 j<=n-3
    for(int j=i+1;j<nums.length-2;j++){
      if(j>i+1 && nums[j-1]==nums[j]){ //TODO:j-1 的值最小为i+1
        continue;
      }

      int newTarget = target -(nums[i]+nums[j]);
      int l = j+1;
      int r = nums.length-1;
      //在[l,r] 中查找两个元素和为 newTarget 的元素
      while(l<r){
        if(nums[l]+nums[r] == newTarget){
          res.add(Arrays.asList(nums[l],nums[r],nums[i],nums[j]));
          while(l<r && nums[l]==nums[l+1]){
            l++;
          }
          while(l<r && nums[r]==nums[r-1]){
            r--;
          }
          l++;
          r--;
        }else if(nums[l]+nums[r] < newTarget){
          l++;
        }else{
          assert (nums[l]+nums[r] > newTarget);
          r--;
        }
      }
    }
  }

  return res;
}

@Test
public void test(){
  //int[] nums = {1, 0, -1, 0, -2, 2};
  int[] nums={0,0,0,0};
  int target =0;
  System.out.println(fourSum(nums,target));
}

4、最接近的三数之和(16)

16. 最接近的三数之和

public int threeSumClosest(int[] nums, int target) {
  Arrays.sort(nums);
  int closet = Integer.MAX_VALUE;
  int res = target; //初始时，能够找到和为 target 的元素
  for(int i=0;i<nums.length;i++){
    if(i>0 && nums[i-1]==nums[i]){
      continue;
    }
    int l=i+1;
    int r=nums.length-1;
    while(l<r){
      int sum = nums[i]+nums[l]+nums[r];
      //TODO：不断接近
      if(Math.abs(sum-target)<=closet){
        closet = Math.abs(sum-target);
        res = sum;
      }
      if(sum < target){
        l++;
      }else if(sum > target){
        r--;
      }else{
        return sum;
      }
    }
  }
  return res;
}

@Test
public void test(){
  int[] nums = {-1,2,1,-4};
  int target = 1;
  System.out.println(threeSumClosest(nums,target));
}

五、灵活选择键值

*1、四数相加 II（454）

454. 四数相加 II

//思路：
//A[i] + B[j] + C[k] + D[l] = 0 等价于
//A[i] + B[j] = - (C[k] + D[l])
//A[i] + B[j] 出现多少次则 - (C[k] + D[l]) 就要出现多少次才能使得等式成立
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
  int N = A.length;

  //统计 A[i]+B[j]出现的次数
  Map<Integer,Integer> records = new HashMap<>();
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      int freq = records.getOrDefault(A[i]+B[j],0);
      records.put(A[i]+B[j],++freq);
    }
  }

  int res=0;
  //如果 - (C[k] + D[l]) == A[i] + B[j]，
  //那么 - (C[k] + D[l]) 的出现次数就是等式能成立几次。
  for(int k=0;k<N;k++){
    for(int l=0;l<N;l++){
      if(records.containsKey(-C[k]-D[l])){
        // recoreds 中存在 -C[k]-D[l],我们知道 recoeds 的键值是 A[i]+B[j]
        // 所以 - (C[k] + D[l]) == A[i] + B[j] 成立
        res += records.get(-C[k]-D[l]);
      }
    }
  }
  return res;
}

@Test
public void test(){
  int[] A = {1, 2};
  int[] B = {-2,-1};
  int[] C = {-1, 2};
  int[] D = {0, 2};
  System.out.println(fourSumCount(A,B,C,D));
}

*2、字母异位词分组（49）

字母异位词分组

public List<List<String>> groupAnagrams(String[] strs) {
  //map存储的是<字符串按照字母排序后得到的新字符串,与之相应的anagrams>
  Map<String,List<String>> records = new
    HashMap<>();
  if(strs!=null){
    for(String str : strs){
      char[] chs = str.toCharArray();
      Arrays.sort(chs); // 所有anagram排序后，得到的字符串是相同的
      String sortStr = new String(chs);  //anagram排序 得到的字符串是唯一的
      if(!records.containsKey(sortStr)){
        records.put(sortStr,new ArrayList<>());
      }
      records.get(sortStr).add(str);
    }
  }
  return new ArrayList<>(records.values());
}

@Test
public void test(){
  String[] strs={"eat", "tea", "tan", "ate", "nat", "bat"};
  System.out.println(groupAnagrams(strs));
}

*3、回旋镖的数量（447）

447. 回旋镖的数量

//思考：
//1、关于时间复杂度的思考：
//O(n^2)的算法可以处理大约 10^4 级别的数据
//O(nlogn)的算法可以处理大约 10^8 级别的数据
//O(n)的算法可以处理大约 10^8 级别的算法
//本题 n<=500, 最差要有O(n^2)

//2、两点之间的距离能否使用 int 类型？
// (-10000)^2+10000^2=2*10^8 在int范围内， 可以使用int类型

//思路：
//(i，j)和(i,k)的距离相等，则i是一个“枢纽”，对于每个点i,遍历其余点到i的距离。
//准备一个查找表记录其他点到点i的距离：
//若到点i的距离相等的点的数量 < 2, 则返回0
//若到点i的距离相等的点的数量 >=2（假设为n）,则有 n*(n-1) 种可能
public int numberOfBoomerangs(int[][] points) {
  int res=0;
  for(int i=0;i<points.length;i++){
    //<到点 i 的距离，点i的距离相等的点的数量>
    Map<Integer,Integer> records = new HashMap<>();
    for(int j=0;j<points.length;j++){
      if(j!=i){ //除非是同一点，这里要考虑元素的顺序，顺序不同，结果不同
        int distance = dis(points,i,j);
        int freq = records.getOrDefault(distance,0);
        records.put(distance,++freq);
      }
    }

    for(Integer dis : records.keySet()){
      int freq = records.get(dis);
      if(freq<2){ // 若到点i的距离相等的点的数量 < 2, 则返回0
        continue;
      }
      //若到点i的距离相等的点的数量 >=2（假设为n）,则有 n*(n-1) 种可能
      res += freq*(freq-1);
    }
  }
  return res;
}

//计算点 i 和 点 j 之间的距离
private int dis(int[][] points,int i,int j){
  int ix=points[i][0],iy=points[i][1];
  int jx=points[j][0],jy=points[j][1];
  return (ix-jx)*(ix-jx)+(iy-jy)*(iy-jy);
}

@Test
public void test(){
  int[][] points={
    {0,0},
    {1,0},
    {2,0}
  };
  System.out.println(numberOfBoomerangs(points));
}

4、最长和谐子序列(594)

594.最长和谐子序列

//思路：
//所谓和谐数组就是数组中只存在两种元素值，假最小值为 num，则最大值为 num+1
public int findLHS(int[] nums) {
  //统计 nums 中数字出现的频率
  Map<Integer,Integer> records = new HashMap<>();
  for(int num : nums){
    int freq = records.getOrDefault(num,0);
    records.put(num,++freq);
  }

  int res = 0;
  for(int num : nums){
    if(records.containsKey(num+1)){
      res = Math.max(res,records.get(num)+records.get(num+1));
    }
  }
  return res;
}

@Test
public void test(){
  int[] nums={1,3,2,2,5,2,3,7};
  System.out.println(findLHS(nums));
}

5、最长连续序列(128)

128. 最长连续序列

//思路：
//最长连续序列，就是从 nums 获取一定数量的数据，并且这些数据是连续变化的
//本题的难点在于时间复杂度要求是 O(n)
//我们知道排序算法最好的时间复杂度就是 O(n*log(n))，所以不能使用排序算法
//使用循环 + map 解决：
//对 map 有： < nums中的数组元素, 该元素所在的最长连续序列的长度 >
public int longestConsecutive(int[] nums) {
  if(nums==null || nums.length==0){
    return 0;
  }
  //< nums中的数组元素, 该元素所在的最长连续序列的长度 >
  Map<Integer,Integer> records = new HashMap<>();

  int res=0;
  for(int num:nums){
    if(records.containsKey(num)){
      continue;
    }
    //获取该元素相邻元素的所在的最长连续序列的长度
    int leftLen = records.getOrDefault(num-1,0);
    int rightLen = records.getOrDefault(num+1,0);
    //len 加入 num 后得到的新的最长连续序列
    int len = leftLen + rightLen + 1;
    res = Math.max(res,len);
    records.put(num,len); //更新长度
    //注意：只要在 [num-leftNum,num+rightLen]
    //范围的元素其最长连续序列都是len。
    //在 for 循环中，我们只要更新边界即可
    records.put(num-leftLen,len);
    records.put(num+rightLen,len);
  }
  return res;
}

@Test
public void test(){
  int[] nums={100, 4, 200, 1, 3, 2};
  System.out.println(longestConsecutive(nums));
}