LeetCode刷题之twoSum两数之和Go语言版
题目描述
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
测试示例
示例 1
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3
输入:nums = [3,3], target = 6
输出:[0,1]
前提约束
- 只会存在一个有效答案
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
解决方案
package twosum
// TwoSum
func TwoSum(nums []int, target int) []int {
for i,a := range(nums){
for j,b := range(nums){
if i == j {
continue
}
if (a + b ) == target{
return []int{i,j}
}
}
}
return nil
}
单元测试
package twosum
import "testing"
func Test_TwoSum(t *testing.T) {
tests := []struct {
name string
nums []int
target int
wantErr bool
}{
{
"2,7,11,15-9",
[]int{2, 7, 11, 15},
9,
false,
},
{
"3,2,4-6",
[]int{3, 2, 4},
6,
false,
},
{
"3,3-6",
[]int{3, 3},
6,
false,
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
idx := TwoSum(tt.nums, tt.target)
if 2 != len(idx) {
t.Errorf("未找到合适的结果")
}
if tt.target != (tt.nums[idx[0]] + tt.nums[idx[1]]) {
t.Errorf("计算错误,结果值%d,期望值%d", tt.nums[idx[0]] + tt.nums[idx[1]], tt.target)
}
})
}
}
进阶
还可以想出一个时间复杂度小于O(n^2)的算法吗?
package twosum
func TwoSum(nums []int, target int) []int {
hmap := make(map[int]int)
for i, a := range nums {
if j, ok := hmap[target-a]; ok{
return []int{i, j}
}
hmap[a] = i
}
return nil
}
题目来源
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。