iT邦幫忙

2021 iThome 鐵人賽

DAY 4
0
Software Development

算法30天系列 第 4

Day.4 Two Pointer

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

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

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

先建立兩個指標,一個放在前面(head),一個放在後面(tail)。
https://ithelp.ithome.com.tw/upload/images/20210911/20129767VO0QxnX5MW.png
2+15 = 17,17比18小
我們把head的index +1,因為這是經過排序的,所以head的下一個一定比較大
https://ithelp.ithome.com.tw/upload/images/20210911/20129767i968x44fVw.png
7 + 15 = 21,21比18大
因為加總比目標數大,所以把tail--,理由同上tail-1的值一定比目前的小,
https://ithelp.ithome.com.tw/upload/images/20210911/20129767TMbOvoSoO8.png
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!


上一篇
Day.3 天秤的兩端
下一篇
Day.5 Slide Window
系列文
算法30天30

尚未有邦友留言

立即登入留言