哈希表

1、快乐数

题目链接：https://leetcode.cn/problems/happy-number/description/

我们可以看到如果有循环的话，直接就输出false就行，那么当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

方法一：哈希表

package com.cky.lianbiao;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class RemoveEle {
    public static boolean isHappy(int n) {
        
        Set<Integer> hash=new HashSet<>();
        while(n!=1&&!hash.contains(n)){
            hash.add(n);
            n=square(n);
        }

        return n==1;
    }
    public static int square(int n){
        int res=0;
        while(n>0){
            int temp=n%10;
            res+=temp*temp;
            n=n/10;
        }
        return res;
    }


    public static void main(String[] args) {
        System.out.println(isHappy(2));
        }

    }

方法二：快慢指针

因为如果有循环的话，会有一个隐形的圆环。

①如果快慢指针相遇了则代表有循环，则直接false

②如果是快乐数，则快指针一定会比慢指针首先到达1

比如 (不用管数值 瞎写的）如果1在偶数则快指针直接遇到了第一个，快指针先到达

这种情况下还是快指针先到达

package com.cky.lianbiao;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;



public class RemoveEle {
    public static boolean isHappy(int n) {

        int slow=n;
        int fast=square(n);
        while(fast!=1&&fast!=slow){
            slow=square(slow);
            fast=square(square(fast));
        }

        return fast==1;
    }
    public static int square(int n){
        int res=0;
        while(n>0){
            int temp=n%10;
            res+=temp*temp;
            n=n/10;
        }
        return res;
    }


    public static void main(String[] args) {
        System.out.println(isHappy(19));
        }

    }

2、三数之和

题目：

https://leetcode.cn/problems/3sum/description/

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n =nums.length;
    Arrays.sort(nums);
    for(int first=0;first<n;first++){
        // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[first] > 0) { 
                return result;
            }
        if(first>0 && nums[first]==nums[first-1]){
            continue;
        }
        int third=n-1;
        int sum=-nums[first];
        for(int second=first+1;second<n;second++){
            if(second>first+1 && nums[second]==nums[second-1]){
                continue;
            }
            while(second<third&&nums[second]+nums[third]>sum){
                        third--;
                    }
 
            if(second==third)
                    break;
            if(third<n-1&&nums[third]==nums[third+1])
            third--;
            if(nums[second]+nums[third]==sum){
               result.add(Arrays.asList(nums[first], nums[second], nums[third]));
            }
        }
    }
    return result;
    }
}

本题用哈希表来解决会比较困难，原因是去重比较复杂，注意这里的去重不是说元素之间的去重 比如[-1,-1,2],而是说不能有两个一样的结果。

首先 我们会考虑三重循环 但是三重循环复杂度 O（n3），那么能否考虑一个相对来说不耗时的呢，就是第二步，去重，对第一个，第二重，第三重都进行去重，如果和原来的一样，就跳过，但是这样子复杂度仍然不变。

接着就是第三步考虑，去掉一个循环，因为第一个循环确定第一个数，第二个循环确定第二个数，那么第三个数，其实可以不用循环，从最右边开始，(但是这要先对数组进行排序)。

3、四树之和

其实和三树之和一样，只不过多了一层循环。

‘https://leetcode.cn/problems/4sum/description/

class Solution {
    public List<List<Integer>> fourSum(int[] nums,int target) {
    List<List<Integer>> result = new ArrayList<>();
    int n =nums.length;
    Arrays.sort(nums);
     if (nums == null || nums.length < 4) {
            return result;
        }
    for(int first=0;first<n;first++){
        if(first>0 && nums[first]==nums[first-1]){
            continue;
        }
        for(int second=first+1;second<n;second++){
            if(second>first+1 && nums[second]==nums[second-1]){
                continue;
            }
            long sum=target-((long)nums[first]+nums[second]);
            int four=n-1;
            for(int third=second+1;third<n;third++){
             if(third>second+1 && nums[third]==nums[third-1]){
                continue;
            }
            while(third<four&&((long)nums[third]+nums[four])>sum){
                        four--;
                    }
            if(third==four)
                    break;
            if(four<n-1&&nums[four]==nums[four+1])
            four--;
            if((long)nums[third]+nums[four]==sum){
               result.add(Arrays.asList(nums[first], nums[second], nums[third],nums[four]));
            }
        }
    }}
    return result;
    }
}

4、两数之和

这个可以用哈希表，因为没有去重，并且需要返回索引。

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

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