# 1. Two Sum

We need to find two numbers in the array that sum to the target value. The problem definition states "

*return indices of the two numbers such that they add up to target.*"The wording made me think of x + y = target. But, when approaching problems, see if the equation can be rewritten that will make it easier to solve. In this case target - x = y.

When iterating through an array we will have the target value and the current item value (x). So, we want to find a value for y that solves the equation.

There are two approaches for finding y. One uses a cache, and the other uses two pointers. There is also a brute force solution of using nested loops, but it is too slow.

I initially solved it using a cache. It is the easier of the two solutions for this question. In this solution, each element of the array is cached as the array is iterated over. It is then a matter of checking the array to see if y exists in it.

def twoSum(self, nums: List[int], target: int) -> List[int]:

cache = {}

for i in range(len(nums)):

diff = target - nums[i]

if diff in cache:

return [cache[diff], i]

else:

cache[nums[i]] = i

return []

However, the problem can also be solved using two pointers. The two pointers method is used for solving the Three Sum problem.

- 1.Sort the array.
- 2.Initialize two pointers (left, right) to the first and last positions in the array.
- 3.Sum the values of the left and right elements.
- 1.If the result is greater than the target value, then move the right pointer to the left (and hence resulting in a smaller sum the next time).
- 2.If the result is less than the result, then move the left pointer needs to the right (resulting in a greater sum the next time).

- 4.Repeat step 3 until the summation equals the target. (The question states there will be one unique answer)

**Example**:

input = [11, 7, 4, 15], target = 18

- 1.sort the array: [4, 7, 11, 15]
- 2.initialize pointers: left = 0 (start of the array) right = 3
- 3.iterate through the array summing the left and right index values and moving the left and right pointers as appropriate:

iteration | left index | right index | sum |
---|---|---|---|

0 | 0 | 3 | 4 + 15 = 19 |

1 | 0 | 2 | 4 + 11 = 15 |

2 | 1 | 2 | 7 + 11 = 18 |

def twoSum(self, nums: List[int], target: int) -> List[int]:

# enumerate returns an iterable object containing tuples of the index and value. We need to store the

# original index of the value after the sorting is performed

sortd = enumerate(nums)

# now sort based on the value

sortd = sorted(sortd, key=lambda x: x[1])

left = 0

right = len(sortd) - 1

while left < right:

# need position 1 here to get the value

summ = sortd[left][1] + sortd[right][1]

if target == summ:

# need position 0 here to get the index. The min,max is done here to ensure

# value is returned with the lowest position listed first.

return [min(sortd[left][0], sortd[right][0]), max(sortd[left][0], sortd[right][0])]

elif summ < target:

left += 1

else:

right -= 1

return []

Last modified 2yr ago