LeetCode算法 | Day7 哈希表：四数相加II、赎金信、三数之和、四数之和

454. 四数相加II

题目：

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
示例：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

解题思路：

这道题可以两两组合，AB组合成一组，CD组合成一组，在AB组中两层for循环遍历并且录入map中，CD组就找加起来刚好等于现有map内相反数的组合，就是需要的全部组合。这里注意count在加的时候不是加一，而是加map中录入的数。

var fourSumCount = function (nums1, nums2, nums3, nums4) {
    const map = new Map();
    let count = 0;
    for (let i = 0; i < nums1.length; i++) {
        for (let j = 0; j < nums2.length; j++) {
            const sum = nums1[i] + nums2[j];
            if (map.has(sum)) {
                const curSum = map.get(sum) + 1;
                map.set(sum, curSum);
            } else {
                map.set(sum, 1);
            }
        }
    }
    for (let i = 0; i < nums3.length; i++) {
        for (let j = 0; j < nums4.length; j++) {
            const sum = nums3[i] + nums4[j];
            if (map.has(-sum)) {
                count += map.get(-sum);
            }
        }
    }
    return count;
};

383. 赎金信

题目：

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。

解题思路：

这道题和242.有效的字母异位词很像，区别只是最终返回值的处理条件，这里如果有小于0说明字母不够用，就无法构成ransomNote。

var canConstruct = function (ransomNote, magazine) {
    const arr = new Array(26).fill(0);
    const codeA =  a .charCodeAt();
    for (let i = 0; i < magazine.length; i++) {
        arr[magazine[i].charCodeAt() - codeA]++;
    }
    for (let i = 0; i < ransomNote.length; i++) {
        arr[ransomNote[i].charCodeAt() - codeA]--;
    }
    return arr.findIndex((item) => item < 0) === -1 ? true : false;
};

15. 三数之和

题目：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重大。

解题思路：

1. 双指针

先对原数组排序，然后定义三个指针，一个指针用来从0到length-1遍历，其他两个依次定义在左右两端，在数组中找到nums[i] + nums[left] + nums[right]=0的数字。

var threeSum = function (nums) {
    let result = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            return result;
        }
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                result.push([nums[i], nums[left], nums[right]])
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
};

注意点：

三个位置都需要去重

位置1根据for循环迭代，这个时候需要保证前一个和他不是重复的
位置2和3是找到后，依次把指针前移或后移，这样可以保证后续没有重复

添加完元素后记得要移动指针，否则会无限循环。

2. 哈希法

对于b去重的解释是如果连续三个元素相等, 则只有nums[j – 1]和nums[j – 2]是有用的。
对于移除set的解释是对于一个nums[i]和nums[j], c只可以用一次, 因此将其从set移除, 后面没用了
对于添加nums[j]的解释是目前set无法找到满足条件的c, 那么将num加入, 同时移动j向后找。

var threeSum = function (nums) {
    let result = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            return result;
        }
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let set = new Set();
        for (let j = i + 1; j < nums.length; j++) {
            if (j > i + 2 && nums[j] === nums[j - 1] && nums[j - 1] === nums[j - 2])
                continue;
            let c = -(nums[i] + nums[j])
            if (set.has(c)) {
                result.push([nums[i], nums[j], c]);
                set.delete(c);
            } else {
                set.add(nums[j]);
            }
        }
    }
    return result;
};

18. 四数之和

题目：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不一样
nums[a] + nums[b] + nums[c] + nums[d] == target
示例：

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

解题思路：
思路和三数之和一样，区别在于目前是两层剪枝和两层去重：

剪枝思考的减少循环的次数，外层剪枝需要满足 nums[k] > target && nums[k] >= 0，内层剪枝需要满足 nums[k] + nums[i] > target && nums[k] + nums[i] >= 0。
去重是题目要求，外层去重需要满足 k > 0 && nums[k] === nums[k – 1]，内层去重需要满足 i > k + 1 && nums[i] === nums[i – 1]。

var fourSum = function (nums, target) {
    let result = [];
    nums.sort((a, b) => a - b);
    for (let k = 0; k < nums.length; k++) {
        if (nums[k] > target && nums[k] >= 0) {
            break;
        }
        if (k > 0 && nums[k] === nums[k - 1]) continue;
        for (let i = k + 1; i < nums.length; i++) {
            if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                break
            }
            if (i > k + 1 && nums[i] === nums[i - 1]) continue;
            let left = i + 1;
            let right = nums.length - 1;
            while (left < right) {
                const sum = nums[k] + nums[i] + nums[left] + nums[right];
                if (sum > target) {
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    result.push([nums[k], nums[i], nums[left], nums[right]])
                    while (left < right && nums[left] === nums[left + 1]) left++;
                    while (left < right && nums[right] === nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
    }
    return result;
};