1.两数之和.md

1.两数之和

/*
 * @lc app=leetcode.cn id=1 lang=typescript
 *
 * [1] 两数之和
 */

// @lc code=start
function twoSum(nums: number[], target: number): number[] {}
// @lc code=end

解法 1: 暴力枚举

• 时间复杂度:
• 空间复杂度:

function twoSum(nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
  return []
}

解法 2: 哈希表

• 时间复杂度:
• 空间复杂度:

function twoSum(nums: number[], target: number): number[] {
  const cache = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (cache.has(nums[i])) return [cache.get(nums[i]), i]
    cache.set(target - nums[i], i)
  }
  return []
}

Case

test.each([
  { input: { nums: [2, 7, 11, 15], target: 9 }, output: [0, 1] },
  { input: { nums: [3, 2, 4], target: 6 }, output: [1, 2] },
])('input: nums = $input.nums, target = $input.target', ({ input: { nums, target }, output }) => {
  expect(twoSum(nums, target)).toEqual(output)
})