跟着卡哥学算法Day 7：哈希表中等题目

454. 四数相加 II 🌟🌟#

题目描述#

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

1
示例 1：
2
输入：["h","e","l","l","o"]
3
输出：["o","l","l","e","h"]
4

5
示例 2：
6
输入：["H","a","n","n","a","h"]
7
输出：["h","a","n","n","a","H"]

解题思路#

四个数组 A、B、C、D
暴力法：O(N^4) A(i) + B(j) + C(k) + D(l) = 0

使用哈希表解决#

遍历 A、B，将 A(i) + B(j) 添加到集合、遍历 C、D，将 C(k) + D(l) 添加到集合，O(N^2)
使用 map 作为哈希表，A(i) + B(j) 的结果作为 key，value 存储相同结果出现的次数
定义 count 保存出现的次数
遍历 C、D，找到 0 - C(k) + D(l) 是否在 map 中，在就count + map[C(k) + D(l)]统计最后的 count

代码#

1
/**
2
 * @param {number[]} nums1
3
 * @param {number[]} nums2
4
 * @param {number[]} nums3
5
 * @param {number[]} nums4
6
 * @return {number}
7
 */
8
var fourSumCount = function (nums1, nums2, nums3, nums4) {
9
  const twoSumMap = new Map()
10
  let count = 0
11

12
  for (let num1 of nums1) {
13
    for (let num2 of nums2) {
14
      const sum = num1 + num2
15
      twoSumMap.set(sum, (twoSumMap.get(sum) || 0) + 1)
16
    }
17
  }
18
  for (let num3 of nums3) {
19
    for (let num4 of nums4) {
20
      const target = 0 - (num3 + num4)
21
      if (twoSumMap.get(target)) {
22
        count += twoSumMap.get(target)
23
      }
24
    }
25
  }
26
  return count
27
}

383. 赎金信 🌟#

力扣链接 🌟

题目描述#

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

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

注意：

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

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

解题思路#

同242.有效的字母异位词

代码#

1
/**
2
 * @param {string} ransomNote
3
 * @param {string} magazine
4
 * @return {boolean}
5
 */
6
var canConstruct = function (ransomNote, magazine) {
7
  const record = new Array(26).fill(0)
8
  const base = 'a'.charCodeAt()
9
  for (let i of magazine) {
10
    record[i.charCodeAt() - base]++
11
  }
12
  for (let j of ransomNote) {
13
    if (!record[j.charCodeAt() - base]) return false
14
    record[j.charCodeAt() - base]--
15
  }
16
  return true
17
}

15. 三数之和 🌟🌟#

力扣链接 🌟🌟

题目描述#

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

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

示例：

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

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

解题思路#

哈希解法#

固定一个数，转换为两数之和，用哈希表找另外两个数，时间复杂度 O(n^2)

1
// for循环固定一个数
2
for (let i = 0; i < nums.length; i++) {
3
  let target = 0 - nums[i]
4
  // 求 两数之和 = target即可
5
}

题目需要去重，三个数都需要去重

代码#

1
function threeSum(nums) {
2
  let result = []
3
  nums.sort((a, b) => a - b)
4

5
  for (let i = 0; i < nums.length; i++) {
6
    // 如果当前数大于0，则不可能找到和为0的三元组
7
    if (nums[i] > 0) break
8

9
    // 去重a
10
    if (i > 0 && nums[i] === nums[i - 1]) continue
11

12
    let set = new Set()
13

14
    for (let k = i + 1; k < nums.length; k++) {
15
      // 去重b=c时的b和c
16
      if (k > i + 2 && nums[k] === nums[k - 1] && nums[k - 1] === nums[k - 2])
17
        continue
18

19
      let target = 0 - (nums[i] + nums[k])
20

21
      if (set.has(target)) {
22
        result.push([nums[i], target, nums[k]])
23
        set.delete(target) // 避免重复
24
      } else {
25
        set.add(nums[k])
26
      }
27
    }
28
  }
29

30
  return result
31
}

双指针法#

排序
固定第一个数 i
左(i + 1)右(nums.length - 1)两个指针，向中间移动；大于 0 时，右指针往左移动，小于 0 时，左指针往右移动
**去重：**第一个数与前一个数相同，则跳过；左指针与下一个数相同，跳过；右指针与上一个数相同，跳过

代码#

1
/**
2
 * @param {number[]} nums
3
 * @return {number[][]}
4
 */
5
var threeSum = function (nums) {
6
  let result = []
7
  nums.sort((a, b) => a - b)
8

9
  const length = nums.length
10
  for (let i = 0; i < length; i++) {
11
    const num = nums[i]
12
    if (num > 0) break
13
    if (num === nums[i - 1]) continue
14

15
    let left = i + 1
16
    let right = length - 1
17
    while (left < right) {
18
      const sum = num + nums[left] + nums[right]
19
      if (sum > 0) {
20
        right--
21
      } else if (sum < 0) {
22
        left++
23
      } else {
24
        result.push([num, nums[left], nums[right]])
25
        while (left < right && nums[left] === nums[left + 1]) left++
26
        while (left < right && nums[right] === nums[right - 1]) right--
27
        left++
28
        right--
29
      }
30
    }
31
  }
32
  return result
33
}

18. 四数之和 🌟🌟#

力扣链接 🌟🌟

题目描述#

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

注意：

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

示例：

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

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

解题思路#

在三数之和的基础上，再套一层 for 循环，也就是固定前两个数

剪枝操作：

不能判断 nums[i] > target 就返回，target 可能为负数，比如 nums = [-4, -3, -2, -1]]，target 为 -5，如果 nums[i] > target 就返回，则无法找到满足条件的四元组
需要判断 num[i] > target && (nums[i] >= 0 || target >= 0)

代码#

1
/**
2
 * @param {number[]} nums
3
 * @param {number} target
4
 * @return {number[][]}
5
 */
6
var fourSum = function (nums, target) {
7
  const result = []
8
  nums.sort((a, b) => a - b)
9

10
  const length = nums.length
11
  for (let i = 0; i < length - 3; i++) {
12
    const fNum = nums[i]
13
    if (fNum > target && (fNum >= 0 || target >= 0)) break
14
    if (fNum === nums[i - 1]) continue
15
    for (let j = i + 1; j < length - 2; j++) {
16
      const sNum = nums[j]
17
      if (j > i + 1 && sNum === nums[j - 1]) continue
18
      let left = j + 1
19
      let right = length - 1
20
      while (left < right) {
21
        const tNum = nums[left]
22
        const lNum = nums[right]
23
        const sum = fNum + sNum + tNum + lNum
24
        if (sum > target) {
25
          right--
26
        } else if (sum < target) {
27
          left++
28
        } else {
29
          result.push([fNum, sNum, tNum, lNum])
30
          while (left < right && tNum === nums[left + 1]) left++
31
          while (left < right && lNum === nums[right - 1]) right--
32
          left++
33
          right--
34
        }
35
      }
36
    }
37
  }
38

39
  return result
40
}

音乐

音乐

454. 四数相加 II 🌟🌟#

题目描述#

解题思路#

使用哈希表解决#

代码#

383. 赎金信 🌟#

题目描述#

解题思路#

代码#

15. 三数之和 🌟🌟#

题目描述#

解题思路#

哈希解法#

代码#

双指针法#

代码#

18. 四数之和 🌟🌟#

题目描述#

解题思路#

代码#

音乐

文章目录