Leetcode #167 Two Sum II
題目跟上一篇的Two Sum是一樣的，差別在array是經排序的。

Two Pointer是一種演算法技巧，大家來體驗一下它的巧妙之處。

ex: array: [2,7,11,15] target: 18

先建立兩個指標，一個放在前面(head)，一個放在後面(tail)。

2+15 = 17，17比18小
我們把head的index +1，因為這是經過排序的，所以head的下一個一定比較大

7 + 15 = 21，21比18大
因為加總比目標數大，所以把tail--，理由同上tail-1的值一定比目前的小，

7+11 = 18 找到了

完整程式:

func twoSum(arr []int, target int) []int {
	headIndex := 0
	tailIndex := len(arr) - 1

	for headIndex < tailIndex{
		sum := arr[headIndex] + arr[tailIndex]
		if sum == target {
			return []int{headIndex + 1, tailIndex + 1}
		}

		if sum > target {
			tailIndex--
		} else {
			headIndex++
		}
	}

	return []int{}
}

這個技巧還可以用來做array、字串的反轉等等
在leetcode有滿多題目會用到這算法。

明天會介紹另外一種算法Silde window~
byebye!