wikijs/算法/哈希.md

title	description	published	date	tags	editor	dateCreated
哈希	哈希算法	true	2024-03-21T11:13:33.616Z	算法	markdown	2024-03-21T11:13:33.616Z

有效字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

function isAnagram(s: string, t: string): boolean {
    if (s?.length !== t.length) return false;
    let hashArr: number[] = new Array(26).fill(0);
    const pivot: number = 'a'.charCodeAt(0);
    for (let i = 0; i < s.length; i++) {
        hashArr[s.charCodeAt(i) - pivot]++
        hashArr[t.charCodeAt(i) - pivot]--
    }
    return hashArr.every((e: number) => e === 0);
};

两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。 示例 1：

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

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的

set

function intersection(nums1: number[], nums2: number[]): number[] {
    const set: Set<number> = new Set();
    const ans: Set<number> = new Set();

    for (const num1 of nums1) {
        set.add(num1);
    }

    for (const num2 of nums2) {
        if (set.has(num2)) {
            ans.add(num2);
        }
    }
    return [...ans];
};

filter

function intersection(nums1: number[], nums2: number[]): number[] {
    return [...new Set(nums1.filter(i => nums2.includes(i)))]
};

开心数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为 1，那么这个数就是快乐数。 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 示例 2：

输入：n = 2 输出：false

reduce算和+set判断存在

function isHappy(n: number): boolean {
    const getN = (n) => {
        return n?.toString()?.split('')?.reduce((sum: number, cur: number) => Number(sum) + cur ** 2, 0);
    }

    const Exit = new Set();
    while (true) {
        n = getN(n);
        if (Exit.has(n)) return false;
        if (n === 1) return true;
        Exit.add(n)
    }
};

余数算和+map判断存在

function isHappy(n: number): boolean {
    const getN = (sum, n) => {
        sum += (n % 10) ** 2
        n = Math.floor(n / 10)
        if (n) {
            return getN(sum, n)
        } else {
            return sum
        }
    }

    const M = new Map();
    while (true) {
        n = getN(0, n);
        if (M.has(n)) return false;
        if (n === 1) return true;
        M.set(n, 1)
    }
};

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2：

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

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

function twoSum(nums: number[], target: number): number[] {
    const M = new Map();

    let i = 0;
    while (i < nums?.length) {
        const val = target - nums[i]

        if (M.has(val)) return [M.get(val), i]
        M.set(nums[i], i++)
    }
    return [];
};

四数之和II

给定四个包含整数的数组列表 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 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 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 #算法公开课

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    let helperMap: Map<number, number> = new Map();
    let resNum: number = 0;
    let tempVal: number | undefined;
    for (let i of nums1) {
        for (let j of nums2) {
            tempVal = helperMap.get(i + j);
            helperMap.set(i + j, tempVal ? tempVal + 1 : 1);
        }
    }
    for (let k of nums3) {
        for (let l of nums4) {
            tempVal = helperMap.get(0 - (k + l));
            if (tempVal) {
                resNum += tempVal;
            }
        }
    }
    return resNum;
};

赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false canConstruct("aa", "ab") -> false canConstruct("aa", "aab") -> true

function canConstruct(ransomNote: string, magazine: string): boolean {
    let ransomArr = new Array(26)?.fill(0);
    ransomNote?.split('')?.forEach((e) => {
        ransomArr[e.charCodeAt(0) - 'a'.charCodeAt(0)] += 1
    })
    magazine?.split('')?.forEach((e) => {
        ransomArr[e.charCodeAt(0) - 'a'.charCodeAt(0)] -= 1
    })
    return !ransomArr.find(e => e > 0)
};

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

function threeSum(nums: number[]): number[][] {
    nums.sort((a, b) => a - b);
    let length = nums.length;
    let left: number = 0,
        right: number = length - 1;
    let resArr: number[][] = [];
    for (let i = 0; i < length; i++) {
    	if (nums[i]>0) {
            return resArr; //nums经过排序后，只要nums[i]>0, 此后的nums[i] + nums[left] + nums[right]均大于0,可以提前终止循环。	
	}
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        left = i + 1;
        right = length - 1;
        while (left < right) {
            let total: number = nums[i] + nums[left] + nums[right];
            if (total === 0) {
                resArr.push([nums[i], nums[left], nums[right]]);
                left++;
                right--;
                while (nums[right] === nums[right + 1]) {
                    right--;
                }
                while (nums[left] === nums[left - 1]) {
                    left++;
                }
            } else if (total < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return resArr;
};

四数之和

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

function fourSum(nums: number[], target: number): number[][] {
    nums.sort((a, b) => a - b);
    let first: number = 0,
        second: number,
        third: number,
        fourth: number;
    let length: number = nums.length;
    let resArr: number[][] = [];
    for (; first < length; first++) {
        if (first > 0 && nums[first] === nums[first - 1]) {
            continue;
        }
        for (second = first + 1; second < length; second++) {
            if ((second - first) > 1 && nums[second] === nums[second - 1]) {
                continue;
            }
            third = second + 1;
            fourth = length - 1;
            while (third < fourth) {
                let total: number = nums[first] + nums[second] + nums[third] + nums[fourth];
                if (total === target) {
                    resArr.push([nums[first], nums[second], nums[third], nums[fourth]]);
                    third++;
                    fourth--;
                    while (nums[third] === nums[third - 1]) third++;
                    while (nums[fourth] === nums[fourth + 1]) fourth--;
                } else if (total < target) {
                    third++;
                } else {
                    fourth--;
                }
            }
        }
    }
    return resArr;
};