README
¶
two sum
1. 问题描述
- 给定一数组如[2,7,11,15]和一目标值9，求数组中两个元素为之和为目标值，这两个元素的下标。
2. 解题思路
- 暴力法。两层循环，第一层循环遍历数组取数m，第二遍循环遍历剩下的数组取数n，如果n = traget - m则返回下标即可。
- map法。定义一个以数组元素为key、下标为value的map，遍历数组取数m，查询map中是否有traget - m为key的元素，如果有，返回下边，如果没有，则将数m作为key，下标作为value存入map，继续遍历。
3. 性能测试
map法为TwoSum1，暴力法为TwoSum2，详见two_sum.go
- 当数组中元素为1W时，benchmark测试结果对比：
➜ 1.two_sum git:(feat/golang) ✗ go test -bench .
goos: darwin
goarch: amd64
pkg: github.com/driverfun/leetcode-in-multi-language/golang/1.two_sum
BenchmarkTwoSumV1-12 3000 443212 ns/op
BenchmarkTwoSumV2-12 50 25868747 ns/op
PASS
ok github.com/driverfun/leetcode-in-multi-language/golang/1.two_sum 2.721s
Documentation
¶
Index ¶
- func ArrayPairSumV2(nums []int) int
- func Exist(board [][]byte, word string) bool
- func FindDisappearedNumbers(nums []int) []int
- func FindMedianSortedArrays(nums1 []int, nums2 []int) float64
- func GetKthElement(nums1, nums2 []int, k int) int
- func LongestConsecutiveV2(nums []int) int
- func MergeV2(nums1 []int, m int, nums2 []int, n int)
- func MinSwapsCouplesV1(row []int) int
- func MinSwapsCouplesV2(row []int) int
- func MinSwapsCouplesV3(row []int) int
- func MinSwapsCouplesV4(row []int) int
- func MyAtoi(str string) int
- func NewUnionFindV2(n int) *unionFindV2
- func NextPermutation(nums []int)
- func ReverseWords(s string) string
- func TwoSumV1(nums []int, target int) []int
- func TwoSumV2(nums []int, target int) []int
- type Heap
- type ListNode
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ArrayPairSumV2 ¶
func FindDisappearedNumbers ¶
func FindMedianSortedArrays ¶
func GetKthElement ¶
func LongestConsecutiveV2 ¶
func MinSwapsCouplesV2 ¶
相比于 v1, 用一个数组表示原 row 的 value 的索引关系。 因为 row 是序列 0...len(row)-1 的一个全排列，所以可以考虑用一个数组表示
func MinSwapsCouplesV4 ¶
func NewUnionFindV2 ¶
func NewUnionFindV2(n int) *unionFindV2
func NextPermutation ¶
func NextPermutation(nums []int)
func ReverseWords ¶
Types ¶
Source Files
¶
- 1.two_sum.go
- 122.best-time-to-buy-and-sell-stock-ii.go
- 128.longest-consecutive-sequence.go
- 136.single-number.go
- 1441.build_an_array_with_stack_operations.go
- 15.3sum.go
- 169.majority-element.go
- 2.two_plus.go
- 20.valid-parentheses.go
- 217.contains-duplicate.go
- 26.remove-duplicates-from-sorted-array.go
- 338.counting-bits.go
- 34.find-first-and-last-position-of-element-in-sorted-array.go
- 344.reverse-string.go
- 4.median-of-two-sorted-arrays.go
- 461.hamming-distance.go
- 48.find_dissappeared_numbers.go
- 485.find_max_consecutive_ones.go
- 50.powx-n.go
- 557.reverse-words-in-a-string-iii.go
- 56.merge-intervals.go
- 561.array_pair_sum.go
- 581.shortest-unsorted-continuous-subarray.go
- 7.reverse-integer.go
- 765.min_swaps_couples.go
- 78.subsets.go
- 79.word-search.go
- 8.string-to-integer-atoi.go
- 88.merge-sorted-array.go
- next-permutation.go
- offer.03.shu-zu-zhong-zhong-fu-de-shu-zi-lcof.go
Click to show internal directories.
Click to hide internal directories.