算法训练营第6天｜454.四数相加II、383.赎金信、15.三数之和、18.四数之和

var fourSumCount = function(nums1, nums2, nums3, nums4) {
  // 用 map 存在 key = sum，value = 次数
  // 因为可能出现有多个相加为 0 的可能性例如[0,0],[0,0],[0,0],[0,0]，一共应该出现 8 次
  let map1 = new Map()
  for (let i = 0; i < nums1.length; i++) {
    for (let j = 0; j < nums2.length; j++) {
      let sum = nums1[i] + nums2[j]
      const v = map1.get(sum)
      if (v !== undefined) {
        map1.set(sum, v + 1)
      } else {
        map1.set(sum, 1)
      }

    }
  }
  let count = 0
  for (let i = 0; i < nums3.length; i++) {
    for (let j = 0; j < nums4.length; j++) {
      let sum = nums3[i] + nums4[j]
      const gap = 0 - sum
      const v = map1.get(gap)
      if (v !== undefined) {
        count += v
      }
    }
  }
  return count
};

var canConstruct = function(ransomNote, magazine) {
  const map = new Map()
  const arr1 = magazine.split('')
  // 记录magazine中数字的次数
  for (let i = 0; i < arr1.length; i++) {
    const v = map.get(arr1[i])
    if (v=== undefined) {
      map.set(arr1[i], 1)
    } else {
      map.set(arr1[i], v + 1)
    }
  }

  const arr2 = ransomNote.split('')
  for (let i = 0; i < arr2.length; i++) {
    const cur = arr2[i]
    const v = map.get(cur)
    console.log(cur, v)
    if (v === undefined || v <= 0 ) {
      // 只要没出现过或者次数用完了就返回 false
      return false
    } else {
      // ransomNote出现过一次就-1
      map.set(cur, v - 1)
    }
  }

  return true

};

var threeSum = function(nums) {
  let result = []
  const newArr = nums.sort((a,b) => a-b)
  for (let i = 0; i < newArr.length; i++) {
    // 排序完的数组，如果当前数字大于 0，则后续不可能比 0 小，不用继续了
    if (newArr[i] > 0) return result
    // 外层循环的去重逻辑，如果当前值和上一个值相等就跳过当前循环
    // 为什么不能判断newArr[i] === newArr[i+1]是因为对于[-1,-1,2]这个数组
    // i-> -1,left -> -1, right -> 2
    // newArr[i] === newArr[i+1] 会**占用** left 指针的位置，让[-1,-1,2]这个解被跳过
    if (newArr[i] === newArr[i-1]) continue
    let left = i + 1
    let right = newArr.length - 1
    while (right > left) {
      if (newArr[i] + newArr[left] + newArr[right] > 0) {
        right --
      } else if (newArr[i] + newArr[left] + newArr[right] < 0) {
        left ++
      } else {
        result.push([newArr[i], newArr[left], newArr[right]])
        // 去重
        // right > left 这里额外的判断其实是优化手段，不要也行，不需要判断那么多次
        while (right > left && newArr[left] === newArr[left+1]){
          left ++
        }
        while (right > left && newArr[right] === newArr[right-1]) {
          right --
        }
        // 这里为什么上面移动完指针后还需要移动指针，是因为
        // [1, -1,-1,0], i -> 1, left -> -1, right -> 0
        // result.push之后其实 left所在的第一个 -1 已经被用掉了
        // 判断newArr[left] === newArr[left+1] 后向右移动 left到第二个-1就终止了，因为下一次判断不满足newArr[left] === newArr[left+1]
        // 此时 left -> 第二个-1，所以这里还需要向右移动
        // 总的来说newArr[left] === newArr[left+1]是判断下一次是否相等，下一次不相等但指针对应的值已经被用过了，所以还需要移动
        left ++
        right --
      }
    }
  }
  return result
};

var fourSum = function(nums, target) {
  const newArr = nums.sort((a,b) => a - b)
  const res = []
  if(newArr.length < 4) return [];
  for (let k = 0; k < newArr.length; k++) {
    // 剪枝操作，当target>0时，如果newArr[k] > target，则说明后续的循环没有意义了
    if (target > 0 && newArr[k] > target) return res
    // 去重操作，当当前元素和上个元素相同时，会得到相同的答案，所以直接跳过
    if (k > 0 && newArr[k] === newArr[k-1]) continue
    for (let i = k + 1; i < newArr.length; i++) {
      // 去重操作，当当前元素和上个元素相同时，会得到相同的答案，所以直接跳过
      // 注意一定要判断i > k + 1
      // 当k=0，i=1，如果nums[1]等于nums[0]，此时i=1是k+1的位置，所以不应该跳过，否则会漏掉所有以k=0和i=1的组合
      if(i > k + 1 && nums[i] === nums[i - 1]) continue;
      let left = i + 1
      let right = newArr.length - 1
      while (right > left) {
        const sum = newArr[k] + newArr[i] + newArr[left] + newArr[right]
        if (sum > target) {
          right --
        } else if (sum < target) {
          left ++
        } else {
          res.push([newArr[k], newArr[i], newArr[left], newArr[right]])
          // 这里的逻辑和三数之和一样，去重操作
          while (right > left && newArr[left] === newArr[left + 1]) {
            left ++
          }
          while (right > left && newArr[right] === newArr[right - 1]) {
            right --
          }
          left ++
          right --
        }
      }

    }
  }

  return res

};