Day.4 Two Pointer

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!