leetcode/lc/1/

[giscus[bot]]

leetcode/lc/1/

多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

https://doocs.github.io/leetcode/lc/1/

[yanglbme]

最简单高效的解法，就是用哈希表

[15807076130]

其他解法
解法一：对于每个元素nums[i]，遍历右侧元素是否存在target-nums[i]。时间复杂度o(n^2)
解法二：先对数组排序，然后双指针分别指向数组开头和结尾，两元素相加，若和>target，则右指针左移，若和<target，则左指针右移，直至找到答案。时间复杂度取决于排序方法

[yanglbme]

这两种解法可以的，不过复杂度高于哈希表的解法

[zhuhui132]

zhuhui 2024.06.04 打卡

[yanglbme]

欢迎评论区打卡留言

[rain84]

Additionally to hash-table you can use approach with 2 pointers.
Formally time complexity will be the same O(n), but technically it should be 2 times faster.
But unfortunately it also comes with code duplication.. 🤷🏻

function twoSum(nums: number[], target: number): number[] {
  const map: Record<number, number> = {}
  const n = nums.length

  for (let l = 0, r = n - 1; l <= r; l++, r--) {
    let v = nums[l]
    let diff = target - v

    if (map[diff] !== undefined) return [map[diff], l]
    map[v] = l

    v = nums[r]
    diff = target - v

    if (map[diff] !== undefined) return [map[diff], r]
    map[v] = r
  }

  return []
}