Besides using one pointer to loop through all elements, you can use two pointers to walk inward from both ends of a linear collection, such as array or string, to check a condition

Apart from that, you can also hash collection elements into a hash table to improve the lookup time

Let walk through this article to explore them in more details

### The 2Sum problem

- Given an array of integers
`a[n]`

and an integer number`k`

as a target sum - Determine whether there is a pair of elements
`a[i]`

and`a[j]`

that sums exactly to`k`

### Example

- Given an array a [1, 3, 7] and k = 8 then the answer is
`true`

, but given k=5 then the answer is`false`

- Given an array a [4, -9, 0, 11, 6, -20, 1, 7] and k = -14 then the answer is
`true`

, but given k = -15 then the answer is`false`

### Approach 1: Brute force

- Try all pairs in array
`a`

to see if any of them add up to`k`

```
```

- Output

```
true
false
true
false
```

- Time complexity: O(n
^{2}) as with each element, the algorithm loops through the array which takes O(n) time - Space complexity: O(1)

### Approach 2: Two pointers

- Sort the array
- Walk two pointers inward from both ends of the array, at each point looking at their sum

```
```

- Output

```
true
false
true
false
```

- Time complexity: O(nlogn) due to the cost of sorting
- Space complexity: O(1)

### Approach 3: Hash table

- Add array elements into a hash table
- For each array element
`a[i]`

, check if existing an element`a[j]`

that`a[j] = k - a[i]`

```
```

- Output

```
true
false
true
false
```

- Time complexity: O(n) as with each element, the algorithm looks up in the hash table which takes O(1) time
- Space complexity: O(n) as the algorithm adds elements into a hash table