Two Sum

on technology

=======

; https://oj.leetcode.com/problems/two-sum/
; # Two Sum
; Given an array of integers, find two numbers such that they add up to a specific target number.
; The function twoSum should return indices of the two numbers such that they add up to the target,
; where index1 must be less than index2. Please note that your returned answers (both index1 and index2)
; are not zero-based.
; You may assume that each input would have exactly one solution.
;
;   Input: numbers={2, 7, 11, 15}, target=9
;   Output: index1=1, index2=2

; HOWTO
; (helper '(2 7 11 15) 9 1 4) => (helper '(2 7 11) 9 1 3) => (helper '(2 7) 9 1 2) => [1 2]

(defn two-sum
  [numbers target]
  (defn helper
    [numbers target start end]
    (if (< (count numbers) 2)
      [-1 -1]
      (let [sum (+ (first numbers) (last numbers))]
        (cond (= sum target)
              [start end]
              (> sum target)
              (helper (butlast numbers) target start (- end 1))
              (< sum target)
              (helper (rest numbers) target (+ start 1) end)))))
  (helper numbers target 1 (count numbers)))

Notice:

  • if head + tail > target: drop tail element to have two sum smaller.
  • if head + tail < target: drop head element to have two sum bigger.
  • if head + tail == target: that’s it.
  • It’s more funny using element than index.
  • It’s more funny using recursive than loop.

PS:

=> (doc butlast)
-------------------------
clojure.core/butlast
([coll])
  Return a seq of all but the last item in coll, in linear time
  nil