LEETCODE - 0001 - 两数之和

379 阅读1分钟

原文链接

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/tw… 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

  1. 遍历输入的数组,计算当前数字需要的另一个数字 n2 = target - n1。
  2. 从额外的map中寻找 n2
    • 如果能找到,则当前数字n1的下标i1和map中存储的下标m[n2]组成答案返回
    • 如果未找到,则记录当前数字的值和下标m[val] = idx

完整代码

Golang

func TwoSum(nums []int, target int) []int {
    m := map[int]int{}

    for i1, n1 := range nums {
        n2 := target - n1
        i2, ok := m[n2]
        if ok {
            return []int{i2, i1}
        }

        m[n1] = i1
    }

    return nil
}

Common Lisp

递归

(defun two-sum (lst tar)
  (two-sum-helper lst tar 0
                  (find-num-index (cdr lst) (- tar (car lst)) 1)))

(defun two-sum-helper (lst tar m n)
  (if (null lst) nil
      (if (numberp n)
          (list m n)
          (two-sum-helper (cdr lst) tar (+ m 1)
                          (find-num-index (cdr lst) (- tar (car lst)) (+ m 2))))))

(defun find-num-index(lst tar n)
  (if (null lst) nil
      (if (eql tar (car lst))
          n
          (find-num-index (cdr lst) tar (+ n 1)))))

非递归

(defun two-sum (lst tar)
  (let ((ht (make-hash-table))
        (l (length lst))
        (n nil))
    (do ((i 0 (+ i 1)))
        ((> i l) nil)
      (setf n (gethash (- tar (car lst)) ht))
      (if (numberp n)
          (return-from two-sum (list n i)))
      (setf (gethash (car lst) ht) i)
      (pop lst))))