给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
来源:力扣(LeetCode) 链接:leetcode-cn.com/problems/tw… 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
- 遍历输入的数组,计算当前数字需要的另一个数字 n2 = target - n1。
- 从额外的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))))