1.哈希

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

复杂度 时间复杂度: O(n)

空间复杂度: O(1)

Code

/**
 * @param {number[]} numS
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numS, target) {
  let obj = {}
  let len = numS.length
  for (let i = 0; i < len; i++) {
    let temp = target - numS[i]
    if (Reflect.has(obj, temp)) {
      console.log([i, obj[temp]])
      return [i, obj[temp]]
    } else {
      obj[numS[i]] = i
    }
  }
}

49. 字母异位词分组 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

const groupAnagrams = function(strs) {
    const obj = {}
    for (const iterator of strs) {
        let arr = Array.from(iterator)
        let temp =  arr.sort().toString()
        if(Reflect.has(obj,temp)) {
            obj[temp].push(iterator)
        }else {
            obj[temp] = [iterator]
        }
    }
    return Object.values(obj)
};

128. 最长连续序列 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

const longestConsecutive = function(nums) {
    let set = new Set(nums)
    let long = 0
    for (const iterator of set) {
        if(!set.has(iterator-1)) {
            let curNum = iterator
            let curLong = 1

            while(set.has(curNum+1)) {
                curNum +=1
                curLong +=1
            }
            long = Math.max(long, curLong)

        }
    }
    return long
};

2.双指针

283. 移动零 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

const moveZeroes = function (nums) {
  const removeEl = (nums, val) => {
    let fast = 0
    let slow = 0
    let len = nums.length
    for (; fast < len; fast++) {
      if (nums[fast] !== val) {
        nums[slow] = nums[fast]
        slow++
      }
    }
    return slow
  }
  let slowIndex = removeEl(nums, 0)
  for (let i = slowIndex; i < nums.length; i++) {
    nums[i] = 0
  }
  return nums
}

11. 盛最多水的容器 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

const maxAreaFn = function (height) {
  let len = height.length
  let first = 0,
    end = len - 1
  let maxArea = 0
  while (first < end) {
    let area = Math.min(height[first], height[end]) * (end - first)
    maxArea = Math.max(maxArea, area)
    if (height[first] < height[end]) {
      first++
    } else {
      end--
    }
  }
  return maxArea
}

15. 三数之和 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

const threeSum = function (nums) {
  let res = []
  let len = nums.length
  if (!nums || len < 3) {
    return res
  }
  nums.sort((a, b) => a - b)
  for (let i = 0; i < len; i++) {
    if (nums[i] > 0) {
      break
    }
    if (i > 0 && nums[i] == nums[i - 1]) continue
    let left = i + 1
    let right = len - 1

    while (left < right) {
      const sum = nums[left] + nums[right] + nums[i]
      if (sum === 0) {
        res.push([nums[i], nums[left], nums[right]])
        while (nums[left] === nums[left + 1]) {
          left++
        }
        while (nums[right] === nums[right - 1]) {
          right--
        }
        left++
        right--
      } else if (sum < 0) {
        left++
      } else if (sum > 0) {
        right--
      }
    }
  }
  return res
}

42. 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

const trap = function (height) {
  let len = height.length
  let left = 0
  let right = len - 1
  let sum = 0
  let leftMax = 0
  let rightMax = 0
  while (left < right) {
    leftMax = Math.max(leftMax, height[left])
    rightMax = Math.max(rightMax, height[right])
    if (height[left] < height[right]) {
      sum += leftMax - height[left]
      left++
    } else {
      sum += rightMax - height[right]
      right--
    }
  }
  return sum
}

3. 二分查找

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

const searchInsert = function (nums, target) {
  let len = nums.length
  let left = 0
  let right = len - 1
  let index = len

  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2)
    if (target <= nums[mid]) {
      index = mid
      right = mid - 1
    } else {
      left = mid + 1
    }
  }
  console.log(index)
  return index
}

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

const searchMatrix = function (matrix, target) {
  const m = matrix.length
  const n = matrix[0].length
  let left = 0
  let right = m * n - 1
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2)
    let value = matrix[Math.floor(mid / n)][mid % n]
    if (target < value) {
      right = mid - 1
    } else if (target > value) {
      left = mid + 1
    } else {
      return true
    }
  }
  return false
}

34. 在排序数组中查找元素的第一个和最后一个位置 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

版权所有

版权归属：tuyongtao1

许可证：署名 4.0 国际 (CC-BY-4.0)