167. Two Sum II - Input Array Is Sorted

Leetcode 問題: 167. Two Sum II - Input Array Is Sorted
Categories:
Tags:

題目

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

在有排序陣列中找出兩個數，使它們的和為 target

答案

Golang

解法 1，假設傳入的整數陣列是 已按照大小排序

func twoSum167Solution1(NumberList []int, finalSumValue int) []int {
	// 起始數字索引
	frontNumberIndex := 0
	// 後方數字索引
	backNumberIndex := len(NumberList) - 1

	for frontNumberIndex < backNumberIndex {
		// 當前方索引沒有超過後方索引，可以繼續搜尋
		// 索引數字總和
		searchNumberSumValue := NumberList[frontNumberIndex] + NumberList[backNumberIndex]

		if searchNumberSumValue == finalSumValue {
			// 「索引數字總和」與「指定數字總和」相同，找到了
			return []int{frontNumberIndex + 1, backNumberIndex + 1}
		}

		if searchNumberSumValue < finalSumValue {
			// 「索引數字總和」小於「指定數字總和」，必需要更大的數字，前方索引往後
			frontNumberIndex++
		} else {
			// 「索引數字總和」大於「指定數字總和」，必需要更小的數字，後方索引往前
			backNumberIndex--
		}
	}

	return nil
}

解法 2，假設傳入的整數陣列是 沒有按照大小排序

func twoSum167Solution2(NumberList []int, finalSumValue int) []int {
	numberReverseMapping := make(map[int]int)
	for currentNumberKey, currentNumberValue := range NumberList {
		// 找尋另一個數字
		anotherNumber := finalSumValue - currentNumberValue
		if otherValueKey, isOtherValueExist := numberReverseMapping[anotherNumber]; isOtherValueExist {
			// 如果有另外一個數字的鍵值存在，回傳其他數值鍵值 + 目前數值鍵值
			return []int{otherValueKey + 1, currentNumberKey + 1}
		}

		// 沒有找到另外一個數字，將此數字存入反向 Mapping 表中
		numberReverseMapping[currentNumberValue] = currentNumberKey
	}

	return nil
}

完整程式碼

package main

import (
	"fmt"
	"os"
)

type Question struct {
	// 參數
	Parameter
	// 答案
	Answer
}

// 參數
type Parameter struct {
	NumberList    []int
	finalSumValue int
}

// 答案
type Answer struct {
	result []int
}

func main() {

	QuestionList := []Question{
		{
			Parameter{[]int{2, 7, 11, 15}, 9},
			Answer{[]int{1, 2}},
		},
		{
			Parameter{[]int{3, 2, 4}, 6},
			Answer{[]int{1, 2}},
		},

		{
			Parameter{[]int{3, 2, 4}, 5},
			Answer{[]int{0, 1}},
		},

		{
			Parameter{[]int{0, 8, 7, 3, 3, 4, 2}, 11},
			Answer{[]int{1, 3}},
		},

		{
			Parameter{[]int{0, 1}, 1},
			Answer{[]int{0, 1}},
		},

		{
			Parameter{[]int{0, 3}, 5},
			Answer{[]int{}},
		},
	}

	fmt.Printf("------------------------Leetcode Problem 167------------------------\n")
	for _, question := range QuestionList {
		// _, p := Question.Answer, Question.Parameter
		param := question.Parameter
		fmt.Printf("【input】:%v       【output】:%v\n", param, twoSum167Solution1(param.NumberList, param.finalSumValue))
		fmt.Printf("【input】:%v       【output】:%v\n", param, twoSum167Solution2(param.NumberList, param.finalSumValue))
		os.Exit(0)
	}
}

func twoSum167Solution1(NumberList []int, finalSumValue int) []int {
	// 起始數字索引
	frontNumberIndex := 0
	// 後方數字索引
	backNumberIndex := len(NumberList) - 1

	for frontNumberIndex < backNumberIndex {
		// 當前方索引沒有超過後方索引，可以繼續搜尋
		// 索引數字總和
		searchNumberSumValue := NumberList[frontNumberIndex] + NumberList[backNumberIndex]

		if searchNumberSumValue == finalSumValue {
			// 「索引數字總和」與「指定數字總和」相同，找到了
			return []int{frontNumberIndex + 1, backNumberIndex + 1}
		}

		if searchNumberSumValue < finalSumValue {
			// 「索引數字總和」小於「指定數字總和」，必需要更大的數字，前方索引往後
			frontNumberIndex++
		} else {
			// 「索引數字總和」大於「指定數字總和」，必需要更小的數字，後方索引往前
			backNumberIndex--
		}
	}

	return nil
}

func twoSum167Solution2(NumberList []int, finalSumValue int) []int {
	numberReverseMapping := make(map[int]int)
	for currentNumberKey, currentNumberValue := range NumberList {
		// 找尋另一個數字
		anotherNumber := finalSumValue - currentNumberValue
		if otherValueKey, isOtherValueExist := numberReverseMapping[anotherNumber]; isOtherValueExist {
			// 如果有另外一個數字的鍵值存在，回傳其他數值鍵值 + 目前數值鍵值
			return []int{otherValueKey + 1, currentNumberKey + 1}
		}

		// 沒有找到另外一個數字，將此數字存入反向 Mapping 表中
		numberReverseMapping[currentNumberValue] = currentNumberKey
	}

	return nil
}

參考資料