two-sum.js

const sparse_find = function(some_nums, target, first) {
    let result = undefined
    
    // Array#some is the only approach (vs. for-loop, for-of,
    // other Array methods, Lodash methods) that both handles
    // sparse-arrays *and* short-circuits
    some_nums.some((second, j) => {
        console.log(first, j+":"+second)
        if (first + second === target) {
            result = j
            return true
        }
    })
    
    return result
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    const indices_over = [],
        indices_under = [],
        
        // Intentionally allowed to be non-integer — if it *is*,
        // triggers the special-case odd-handling below
        half = target / 2
    
    let saw_half_at = undefined
    
    for (let i = 0; i < nums.length; i++) {
        const num = nums[i]
        
        // Reject numbers that couldn't possibly pair up
        if (num > target) continue
        
        // Handle the case where the pair is [half, half].
        // Will only ever trigger for odd `target`s.
        if (num === half) {
            if (saw_half_at !== undefined)
                return [saw_half_at, i]
            saw_half_at = i
        }
        
        // Finally, split the test-space in two: if the current number is *less*
        // than half, then we only need to test it against previous values that
        // are *more* than half.
        if (num < half) {
            if (undefined !== (result = sparse_find(indices_over, target, num)))
                return [result, i]
            
            indices_under[i] = num
        } else {
            if (undefined !== (result = sparse_find(indices_under, target, num)))
                return [result, i]
            
            indices_over[i] = num
        }
    }
    
    throw "Unreachable"
}