Golang每日一练(leetDay0006)
目录
16. 最接近的三数之和 3Sum Closest ★★
17. 电话号码的字母组合 Letter-combinations-of-a-phone-number ★★
18. 四数之和 4Sum ★★
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
16. 最接近的三数之和 3Sum Closest
给你一个长度为 n
的整数数组 nums
和 一个目标值 target
。请你从 nums
中选出三个整数,使它们的和与 target
最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1:
输入:nums = [-1,2,1,-4], target = 1 输出:2 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2:
输入:nums = [0,0,0], target = 1 输出:0
提示:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4
代码: 双指针
package main
import (
"fmt"
"sort"
)
func threeSumClosest(nums []int, target int) int {
sort.Ints(nums) // 先排序
res := nums[0] + nums[1] + nums[2]
for i := 0; i < len(nums)-2; i++ {
l, r := i+1, len(nums)-1 // 双指针
for l < r {
sum := nums[i] + nums[l] + nums[r]
if abs(sum-target) < abs(res-target) {
res = sum
}
if sum == target {
return target
} else if sum < target {
l++
} else {
r--
}
}
}
return res
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func main() {
fmt.Println(threeSumClosest([]int{-1, 2, 1, -4}, 1))
fmt.Println(threeSumClosest([]int{0, 0, 0}, 1))
}
输出:
2
0
循环暴力法:
package main
import "fmt"
func threeSumClosest(nums []int, target int) int {
res, dif := 0, 20000 //见提示中参数的范围,设置20000足够
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
for k := j + 1; k < len(nums); k++ {
sum := nums[i] + nums[j] + nums[k]
tmp := sum - target
if tmp < 0 {
tmp = target - sum
}
if tmp < dif {
dif, res = tmp, sum
}
}
}
}
return res
}
func main() {
fmt.Println(threeSumClosest([]int{-1, 2, 1, -4}, 1))
fmt.Println(threeSumClosest([]int{0, 0, 0}, 1))
}
17. 电话号码的字母组合 Letter-combinations-of-a-phone-number
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = "23" 输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
输入:digits = "" 输出:[]
示例 3:
输入:digits = "2" 输出:["a","b","c"]
提示:
0 <= digits.length <= 4
digits[i]
是范围['2', '9']
的一个数字。
代码:
package main
import (
"fmt"
)
func letterCombinations(digits string) []string {
if digits == "" {
return []string{}
}
dict := map[byte][]string{
'2': {"a", "b", "c"},
'3': {"d", "e", "f"},
'4': {"g", "h", "i"},
'5': {"j", "k", "l"},
'6': {"m", "n", "o"},
'7': {"p", "q", "r", "s"},
'8': {"t", "u", "v"},
'9': {"w", "x", "y", "z"},
}
res := []string{""}
for i := 0; i < len(digits); i++ {
temp := []string{}
for j := 0; j < len(res); j++ {
for k := 0; k < len(dict[digits[i]]); k++ {
temp = append(temp, res[j]+dict[digits[i]][k])
}
}
res = temp
}
return res
}
func main() {
fmt.Println(letterCombinations("23"))
fmt.Println(letterCombinations(""))
fmt.Println(letterCombinations("2"))
}
输出:
[ad ae af bd be bf cd ce cf]
[]
[a b c]
18. 四数之和 4Sum
给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和d
互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0 输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8 输出:[[2,2,2,2]]
提示:
1 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
代码:
package main
import (
"fmt"
"sort"
)
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums) // 先排序
res := [][]int{}
for i := 0; i < len(nums)-3; i++ {
if i > 0 && nums[i] == nums[i-1] { // 跳过重复的元素
continue
}
for j := i + 1; j < len(nums)-2; j++ {
if j > i+1 && nums[j] == nums[j-1] { // 跳过重复的元素
continue
}
l, r := j+1, len(nums)-1 // 双指针
for l < r {
sum := nums[i] + nums[j] + nums[l] + nums[r]
if sum == target {
res = append(res, []int{nums[i], nums[j], nums[l], nums[r]})
for l < r && nums[l] == nums[l+1] { // 跳过重复的元素
l++
}
for l < r && nums[r] == nums[r-1] { // 跳过重复的元素
r--
}
l++
r--
} else if sum < target {
l++
} else {
r--
}
}
}
}
return res
}
func main() {
fmt.Println(fourSum([]int{1, 0, -1, 0, -2, 2}, 0))
fmt.Println(fourSum([]int{2, 2, 2, 2, 2}, 8))
}
输出:
[[-2 -1 1 2] [-2 0 0 2] [-1 0 0 1]]
[[2 2 2 2]]
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
| Golang每日一练 专栏 |
| Python每日一练 专栏 |
| C/C++每日一练 专栏 |
| Java每日一练 专栏 |