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
}

参考资料