# TwoSum

### Description of Problem

Given a list of integers and a target, find two integers that sum to the target.

### Walking inward algorithm

TwoSum: Scans sorted list, `values`, for two entries that sum to `target`.

1. If `values.length < 2` then return `[]`

2. Calculate `sum = values.smallest + values.largest`.

3. If `sum > target` then we deduce that if the largest number added to the smallest number is greater than the target then the largest number added to any other number on the list will also be greater than the target. Remove `values.largest` from `values` and goto 1.

4. If `sum < target` then we deduce that if the smallest number added to the largest number is less than the target then the smallest number added to any other number on the list will also be less than the target. Remove `values.smallest` from `values` and goto 1.

5. If `sum = target` then return `[values.smallest, values.largest]`.

#### Example

Input: `[0, 2, 11, 19, 90], 21`

0 2 11 19 90

Sum smallest and largest remaining values: `0 + 90 > 21`

If `90` is greater than `21` when added to the smallest number, `0`, then we can conclude that `90` is also greater than `21` when added to any number in the list, and therefore eliminate `90` as belonging to a valid solution.

0 2 11 19 90

Sum smallest and largest remaining values: `0 + 19 < 21`

If `0` is less than `21` when added to the largest remaining number, `19`, then we can conclude that `0` is also less than `21` when added to any number in the list, and therefore can eliminate `0` as belonging to a valid solution.

0 2 11 19 90

Sum smallest and largest remaining values: `2 + 19 = 21`

Valid solution found.

#### VB.NET

``````Function TwoSum(values As List(Of Integer), target As Integer) As Integer()

Dim A As Integer = 0
Dim B As Integer = values.Count - 1

Do
If A >= B Then Return New Integer() {}

' Mmmm.. dim sum.
Dim sum As Integer = values(A) + values(B)

If sum > target Then
B -= 1
ElseIf sum < target Then
A += 1
Else
Return New Integer() {values(A), values(B)}
End If

Loop

End Function``````