Leetcode 454.四数相加II

题目：454.四数相加II

初始思路

四个数组求和，可以参考242.有效的字母异位词，四个数组两两分组。

代码

  1. var fourSumCount = function (nums1, nums2, nums3, nums4) {
  2.     // key放nums和nums2两数之和，value放两数之和出现的次数。
  3.     const map = new Map()
  4.     let count = 0
  6.     // 遍历nums1和nums2数组，统计两个数组元素之和，和出现的次数，放到map中。
  7.     for (let n1 of nums1) {
  8.         for (let n2 of nums2) {
  9.             const sum1 = n1 + n2
  10.             if (map.has(sum1)) {
  11.                 map.set(sum1, map.get(sum1) + 1)
  12.             } else {
  13.                 map.set(sum1, 1)
  14.             }
  15.         }
  16.     }
  18.     // 在遍历nums3和nums4数组，找到如果 0-(n3+n4) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
  19.     for (let n3 of nums3) {
  20.         for (let n4 of nums4) {
  21.             const sum2 = - n3 - n4
  22.             if (map.has(sum2)) {
  23.                 count += map.get(sum2)
  24.             }
  25.         }
  26.     }
  28.     return count
  29. };

感想

  1. 思路参考242.有效的字母异位词
  2. 要注意map的key和value都存放的是什么，key放nums和nums2两数之和，value放两数之和出现的次数。
  3. 在遍历的过程中，如果这个和没出现过，次数就设置为1，如果出现过就获取这个和的value值。
  4. 在遍历nums3和nums4的时候，直接找-(n3+n4)出现的次数即可。

Leetcode 383.赎金信

题目：383.赎金信

初始思路

思路参考242.有效的字母异位词。还是先记录magazine中的字符，然后再ransomNote中对比查找。

代码

  1. var canConstruct = function (ransomNote, magazine) {
  2.     if (ransomNote.length > magazine.length) return false
  3.     const resSet = new Array(26).fill(0)
  4.     const base = 'a'.charCodeAt()
  6.     for (let s of magazine) {
  7.         resSet[s.charCodeAt() - base]++
  8.     }
  9.     for (let s of ransomNote) {
  10.         // 如果ransomNote中出现了magazine不存在的字符
  11.         if (!resSet[s.charCodeAt() - base]) return false
  12.         // 使用过就减1，因为magazine中的字符不能出现多次
  13.         resSet[s.charCodeAt() - base]--
  14.     }
  15.     return true
  16. };

感想

  1. 因为题目说了只有小写字母，所以用数组更方便。
  2. 要熟练掌握这种题目的写法。

Leetcode 15.三数之和

题目：15.三数之和

初始思路

没什么思路，看到题解才理解一点，但是res数组去重还是有点难理解。

代码

  1. var threeSum = function (nums) {
  2.     const res = []
  3.     const len = nums.length
  4.     if (nums == null || len < 3) return res
  5.     // 数组排序
  6.     nums.sort((a, b) => a - b)
  8.     for (let i = 0; i < len; i++) {
  9.         let left = i + 1, right = len - 1
  11.         // 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
  12.         if (nums[i] > 0) break
  13.         // 如果 nums[i] = nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
  14.         if (i > 0 && nums[i] === nums[i - 1]) continue
  16.         while (left < right) {
  17.             let sum = nums[i] + nums[left] + nums[right]
  18.             if (sum < 0) left++
  19.             else if (sum > 0) right--
  20.             else {
  21.                 res.push([nums[i], nums[left], nums[right]])
  22.                 // 当 sum = 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
  23.                 while (left < right && nums[left] === nums[left + 1]) {
  24.                     left++
  25.                 }
  26.                 // 当 sum = 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
  27.                 while (left < right && nums[right] === nums[right - 1]) {
  28.                     right--
  29.                 }
  30.                 left++
  31.                 right--
  32.             }
  33.         }
  35.     }
  36.     return res
  37. };

感想

  1. 使用双指针法，题解：https://leetcode.cn/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
  2. 三元组需要做去重操作。这个很细节，贴上代码随想录的截图。
  3. image.png
  4. 时间复杂度：O(n2)，从O(n3)降了一阶。

Leetcode 18.四数之和

题目：18.四数之和

初始思路

和三数之和思路类似，需要再套一层for循环

代码

  1. var fourSum = function (nums, target) {
  2.     const res = []
  3.     const len = nums.length
  4.     if (nums == null || len < 4) return res
  5.     // 数组排序
  6.     nums.sort((a, b) => a - b)
  8.     for (let i = 0; i < len; i++){
  9.         // 如果 nums[i] = nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
  10.         if (i > 0 && nums[i] === nums[i - 1]) continue
  12.         for (let j = i + 1; j < len - 2; j++){
  13.             // 去重
  14.             if (j > i + 1 && nums[j] === nums[j - 1]) continue
  15.             let left = j + 1, right = len - 1
  17.             while (left < right) {
  18.                 let sum = nums[i] + nums[j] + nums[left] + nums[right]
  19.                 if (sum < target) {
  20.                     left++
  21.                     continue
  22.                 }
  23.                 if (sum > target) {
  24.                     right--
  25.                     continue
  26.                 }
  27.                 res.push([nums[i], nums[j], nums[left], nums[right]])
  28.                 while (left < right && nums[left] === nums[left + 1]) {
  29.                     left++
  30.                 }
  31.                 while (left < right && nums[right] === nums[right - 1]) {
  32.                     right--
  33.                 }
  34.                 left++
  35.                 right--
  36.             }
  37.         }
  38.     }
  40.     return res
  41. };

感想

  1. 好难写，好崩溃。但是思路跟上一题还是一样的。
  2. 多练练吧，今天有点怠惰了。
  3. 时间复杂度：O(n3)，从O(n4)降了一阶。