# leetcode刷题记录Array篇(1&4～Two Sum&Median of Two Sorted Arrays)

L千年老妖 · · 873 次点击 · · 开始浏览

##### 今天写了一道比较简单的和一道难的
###### #Two Sum

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

golang代码：

``````package main

import (
"fmt"
)

func main() {
nums := []int{2, 7, 11, 15}
fmt.Println(twoSum(nums, 9))
}

//自己的版本 O(n^2)
// func twoSum(nums []int, target int) []int {
//     arr := []int{}
//     for index, val := range nums {
//         for index1, val2 := range nums {
//             if val+val2 == target && index != index1 {
//                 arr = []int{index, index1}
//                 return arr
//             }
//         }
//     }
//     return arr
// }

//时间复杂度小的 O(n)
func twoSum(nums []int, target int) []int {

arr := []int{}
container := make(map[int]int)
for i := 0; i < len(nums); i++ {
if xy, ok := container[target-nums[i]]; ok && xy != i {
arr = []int{container[target-nums[i]], i}
return arr
}
container[nums[i]] = i
}
return arr
}``````
###### #

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

golang代码:

``````package main

import (
"fmt"
)

func main() {
nums1 := []int{1, 87, 9}
nums2 := []int{2, 5, 6}
fmt.Println(findMedianSortedArrays(nums1, nums2))
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {

l1, l2 := len(nums1), len(nums2)
numbers1 := make([]float64, l1)
numbers2 := make([]float64, l2)

//合并两个数组
mergeArr := make([]float64, len(nums1)+len(nums2))
for i, val := range nums1 {
numbers1[i] = float64(val)
}
for i, val := range nums2 {
numbers2[i] = float64(val)
}
copy(mergeArr, numbers1)
copy(mergeArr[len(nums1):], numbers2)

//排序（冒泡）
var temp float64
var middle float64
length := len(mergeArr)

for i := 0; i < length-1; i++ {
for j := 0; j < length-i-1; j++ {
if mergeArr[j] > mergeArr[j+1] {
temp = mergeArr[j]
mergeArr[j] = mergeArr[j+1]
mergeArr[j+1] = temp
}
}
}
if length == 0 {
middle = 0
} else if length%2 == 0 {
fmt.Println((mergeArr[length/2] + mergeArr[length/2-1]) / 2)
middle = (mergeArr[length/2] + mergeArr[length/2-1]) / 2
} else {
middle = float64(mergeArr[length/2])
}
return middle
}``````

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传
##### 今天写了一道比较简单的和一道难的
###### #Two Sum

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

golang代码：

``````package main

import (
"fmt"
)

func main() {
nums := []int{2, 7, 11, 15}
fmt.Println(twoSum(nums, 9))
}

//自己的版本 O(n^2)
// func twoSum(nums []int, target int) []int {
//     arr := []int{}
//     for index, val := range nums {
//         for index1, val2 := range nums {
//             if val+val2 == target && index != index1 {
//                 arr = []int{index, index1}
//                 return arr
//             }
//         }
//     }
//     return arr
// }

//时间复杂度小的 O(n)
func twoSum(nums []int, target int) []int {

arr := []int{}
container := make(map[int]int)
for i := 0; i < len(nums); i++ {
if xy, ok := container[target-nums[i]]; ok && xy != i {
arr = []int{container[target-nums[i]], i}
return arr
}
container[nums[i]] = i
}
return arr
}``````
###### #

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

golang代码:

``````package main

import (
"fmt"
)

func main() {
nums1 := []int{1, 87, 9}
nums2 := []int{2, 5, 6}
fmt.Println(findMedianSortedArrays(nums1, nums2))
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {

l1, l2 := len(nums1), len(nums2)
numbers1 := make([]float64, l1)
numbers2 := make([]float64, l2)

//合并两个数组
mergeArr := make([]float64, len(nums1)+len(nums2))
for i, val := range nums1 {
numbers1[i] = float64(val)
}
for i, val := range nums2 {
numbers2[i] = float64(val)
}
copy(mergeArr, numbers1)
copy(mergeArr[len(nums1):], numbers2)

//排序（冒泡）
var temp float64
var middle float64
length := len(mergeArr)

for i := 0; i < length-1; i++ {
for j := 0; j < length-i-1; j++ {
if mergeArr[j] > mergeArr[j+1] {
temp = mergeArr[j]
mergeArr[j] = mergeArr[j+1]
mergeArr[j+1] = temp
}
}
}
if length == 0 {
middle = 0
} else if length%2 == 0 {
fmt.Println((mergeArr[length/2] + mergeArr[length/2-1]) / 2)
middle = (mergeArr[length/2] + mergeArr[length/2-1]) / 2
} else {
middle = float64(mergeArr[length/2])
}
return middle
}``````