未分類

Two Sum II - Input array is sorted

Array, BinarySearch, Go, LeetCode, TwoPointers

Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

1
2
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
提示 解題應用
Array Array/Slice
TwoPointers 記錄index位置

Default:

1
2
3
func twoSum(numbers []int, target int) []int {
}

解答思路:

如果是在無序的狀況下可能要用hashmap來找，不過有事先排序的話就能同時從陣列左右兩邊開始找起，當陣列的最左與最右值相加大於目標值時，表示總合太大將右側的index向內推一點找比較小的值並重新判斷，又當總合小於目標值時表示太小，將左側的index向內推一點找比較大的值並再次判斷，最後如果找到剛好等於目標值的情況就放入結果之中並向上回傳。

程式碼解說:

因為有事先排序所以就能同時從陣列左右兩邊開始找起，一開始當然就是先計算左右兩邊值的總合，如果總合剛好為目標值就將兩邊的index+1放入結果之中(因為題目要的index是從1開始而非0)並結束迴圈向上回傳，最後如果總合大於目標值表示太大，此時就將右邊的index向前推並再次判斷，反之如果總合小於目標值表示太小則將左邊的index向後推，一直找到當左邊的位置超過右邊才停止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var sum int
var front int
var result []int
rear := len(numbers) - 1
for front < rear {
	sum = numbers[front] + numbers[rear]
	if sum == target {
		result = []int{front + 1, rear + 1}
		break
	} else if sum > target {
		rear--
	} else {
		front++
	}
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func twoSum(numbers []int, target int) []int {
	var sum int
	var front int
	var result []int
	rear := len(numbers) - 1
	for front < rear {
		sum = numbers[front] + numbers[rear]
		if sum == target {
			result = []int{front + 1, rear + 1}
			break
		} else if sum > target {
			rear--
		} else {
			front++
		}
	}
	return result
}

總結:

要從有序的陣列中找出2個值總合為目標值的結果，因為有事先排序所以就能同時從陣列左右兩邊開始找起，當陣列的最左與最右值相加大於目標值時，表示總合太大將右側的index向內推一點找比較小的值並重新判斷，又當總合小於目標值時表示太小，將左側的index向內推一點找比較大的值並再次判斷，最後如果找到剛好等於目標值的情況就放入結果之中並向上回傳。

分享到