# 求个two sum的lisp解法

``````⎕IO←0
ts←{⊃(⍵⍳⍨,∘.+⍨⍺)⌷(,⍳2/≢⍺),⊂⍬}

2 7 11 15 ts 9
0 1
``````
``````(define (ts vec n)
(let ([l (vector-length vec)])
(let rec ([i1 0])
(and (< i1 l)
(or
(let rec2 ([i2 0])
(and (< i2 l)
(if (= (+ (vector-ref vec i1)
(vector-ref vec i2))
n)
(list i1 i2)
(rec2 (1+ i2)))))
(rec (1+ i1)))))))

> (ts (vector 2 7 11 15) 9)
(0 1)
``````

3 个赞

scheme用来指导思路, 写psudocode, 用来实现, 一年半载, 觉着你做不到第十道题目.

Python呗

1)两遍遍历

``````  import unittest
from typing import List

class Solution1:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)-1):  #
complement = target - nums[i]
for j in range(i+1, len(nums)):# linear search
if complement == nums[j]:
return [i, j]
return None
``````
1. hashtable-1 (构建与查询分开)
``````  # Two Pass hash table
class Solution2():
def twoSum(self, nums: List[int], target: int) -> List[int]:
lookup = {nums[i]:i for i in range(len(nums))}

for i in range(len(nums)):
complement = target - nums[i]
j = lookup.get(complement) #hash table to search
if j != None and j != i: # 不与前面的重复
return [i, j]
return []
``````

3)hashtable-2 (构架与查询同时进行)

``````  # One pass solution
class Solution3: #Single Pass Approach
def twoSum(self, nums, target) -> List[int]:
# error case
if len(nums) < 1:
return -1

lookup = {}
# 逆向的方法.
for i in range(len(nums)):
complement = target - nums[i]
if complement in lookup:
return [i, lookup[complement]]
else:
lookup[nums[i]] = i  #构建lookup
#        return []
``````
1 个赞

elisp:

``````(defun two-sum (target nums i j)
(if (= target (+ (aref nums i) (aref nums j)))
(vector i j)
(if (< j (1- (length nums)))
(two-sum target nums i (1+ j))
(two-sum target nums (1+ i) (+ i 2)))))

(two-sum 9 [2 7 11 15] 0 1)
;; => [0 1]
``````
3 个赞

Abstract Algebra: A Computational Approach 有个 function `ssub`。取 {0,1…,N} 的 K-element subset。

``````      ⎕IO←0
2 ssub 4
0 1
0 2
1 2
0 3
1 3
2 3
⎕vr 'ssub'
∇ ssub←{
[1]        ⍝ LISTS ALL K-ELEMENT SUBSETS OF  ⍳N. ORIGIN DEPENDENT.
[2]        S←derr∧/(⍺≥0),(⍺≤⍵),(1=⍴⍺),(1=⍴⍵),(N=⌊N←,⍵),K=⌊K←,⍺
[3]        K{
[4]            ∨/⍺=0 1:⍺((!,⊣)⍴∘⍳⊢)⍵
[5]            X←(⍳N)∘.>⍨⎕IO⌷⍉T←1+(⍺-1)∇ N←⍵-1
[6]            ((,X)/(⍴,X)⍴⍳N),(+/X)⌿T
[7]        }N
[8]    }
``````

``````ts←{(⍵∊⍨+/⍺[I])/[0]I←2 ssub≢⍺}
``````

``````def two_sum(nums, target):

for x in nums:
complement = target - x
sub_nums = nums.copy()
sub_nums.remove(x)

if sub_nums.__contains__(complement):
return [x, complement]
two_sum([2, 7, 11, 15], 9)
``````

``````(defun two-sum (nums target)
(try nums)
)

(defun try (nums)
(let ((copy nums)
(x (car nums))
(complement (- target x)))
(cond
((null x) '())
((memberp complement (remove-first x copy))
(list x complement))
(t (try (cdr nums)))
)))
``````

``````((memberp complement (remove-first x copy))
``````

``````(defun two-sum (nums target)
(try nums)
)

(defun try (nums)
(let ((copy nums)
(x (car nums))
(complement (- target x)))
(cond
((null x) '())
((memberp complement (remove-first x copy))
(list x complement))
(t (try (cdr nums)))
)))

(defun remove-first (item sequence)
(filter (lambda (x) (not (= x item)))
sequence))

(defun filter (predicate sequence)
(cond ((null sequence) nil)
((funcall predicate (car sequence))
(cons (car sequence)
(filter predicate
(cdr sequence))))
(t  (filter predicate
(cdr sequence)))))

(defun memberp(item x)
(cond ((null x) 'false)
((equal item (car x)) x)
(t (memq item (cdr x)))))

(defvar nums (list 2 7 11 15))
(defvar target 9)
(two-sum nums target)
``````

``````let: Symbol’s value as variable is void: x
``````

let的用法或者上面的解法有什么问题?

https://www.gnu.org/software/emacs/manual/html_node/elisp/Local-Variables.html

1 个赞

1. 如果真的拒绝状态，想要「纯函数式」，Racket 里有 immutable hash（性能比 mutable hash 略差）；当然，你甚至还可以用 assoc list。而且它们都实现了 gen:dict 这个 generic。
3. 个人愚见：two sum 这种高度面向刷题的问题，关键就是用 hashmap 降低时间复杂度吧。 如果一定要所谓的纯正函数式体验，那就递归走起，用 naive 的 O(n^2) 算法呗，这个本来就很自然。
如果是 Scheme 的话，srfi-42 eager comprehension 可以让你的编程体验好一些；如果是用 Racket 的话，用 for/first + in-indexed（针对这题）体验会好不少。
1 个赞

leetcode我之后找工作时会用cc刷一遍的，现在用racket写纯属放松下

1 个赞

Project Euler 太赞了！

emm… 边看common lisp文档边写的

``````(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))))
``````

``````TwoSum[array_, target_] :=
SelectFirst[Subsets[Range[Length[array]], {2}],
Total[Part[array, #]] == target &] - 1
``````

``````TwoSum[array_, target_] :=
Fold[Replace[#1[target - #2], {
_?MissingQ :> Append[#1, {
#2 -> #1["length"],
"length" -> #1["length"] + 1
}],
res_ :> Throw[{res, #["length"]}]
}] &, <|"length" -> 0|>, array] // Catch
``````