网站开发的预算,网站设计费用入哪个会计科目,杭州网络安全公司,北京seo公司工作目录
一、两数之和
二、两数之和 II - 输入有序数组
三、两数之和 III - 数据结构设计
四、两数之和 IV - 输入 BST#xff08;二叉搜索树#xff09;
五、三数之和
六、四数之和 一、两数之和
题目#xff1a;1. 两数之和
参考力扣题解#xff1a;. - 力扣#x…目录
一、两数之和
二、两数之和 II - 输入有序数组
三、两数之和 III - 数据结构设计
四、两数之和 IV - 输入 BST二叉搜索树
五、三数之和
六、四数之和 一、两数之和
题目1. 两数之和
参考力扣题解. - 力扣LeetCode
官方两种解法第一种是暴力枚举第二种是哈希表。这两种解法都比较简单实现起来也不复杂。
这里我自己使用golang的对象方式写了一个供参考
type twoSumData struct {nums []inttarget inthashTable map[int]int
}func (t *twoSumData) twoSumBase() []int {n : len(t.nums)if n 1 {return nil}for i : 0; i n; i {for j : i 1; j n; j {if t.nums[i]t.nums[j] t.target {return []int{i, j}}}}return nil
}func (t *twoSumData) twoSumHashTable() []int {n : len(t.nums)if n 1 {return nil}for i : 0; i n; i {if j, ok : t.hashTable[t.target-t.nums[i]]; ok {return []int{i, j}}t.hashTable[t.nums[i]] i}return nil
}func twoSum(nums []int, target int) []int {data : twoSumData{nums: nums,target: target,hashTable: make(map[int]int),}return data.twoSumHashTable()
}
二、两数之和 II - 输入有序数组
题目167. 两数之和 II - 输入有序数组
还是基于前面的结构体使用双指针从两侧往中间找到符合条件的结果。
func (t *twoSumData) twoSumForSortNums() []int {nums : t.numsn : len(nums)left, right : 0, n-1for left right {sum : nums[left] nums[right]if sum t.target {return []int{left 1, right 1}} else if sum t.target {left} else {right--}}return nil
}func twoSum(nums []int, target int) []int {data : twoSumData{nums: nums,target: target,hashTable: make(map[int]int),}return data.twoSumForSortNums()
}
三、两数之和 III - 数据结构设计
题目170. 两数之和 III - 数据结构设计
使用双指针查询
type TwoSum struct {nums []inttarget int
}func Constructor() TwoSum {return TwoSum{nums: make([]int, 0),target: 0,}
}func (this *TwoSum) Add(number int) {this.nums append(this.nums, number)
}func (this *TwoSum) Find(value int) bool {sort.Ints(this.nums)left, right : 0, len(this.nums)-1for left right {sum : this.nums[left] this.nums[right]if sum value {return true} else if sum value {left} else {right--}}return false
}
四、两数之和 IV - 输入 BST二叉搜索树
题目653. 两数之和 IV - 输入二叉搜索树
这个题目实际上就是在前两题的基础上将输入修改为二叉搜索树。
题目的解法有个比较简单的方法我们将二叉搜索树给换成数组然后调用一、二题的函数即可。
比较复杂的方法就是利用二叉搜索树的特点二叉搜索树必然满足root.left.val root.val root.right.val
可以参考下官方题解两数之和 IV - 输入 BST - 力扣官方题解
五、三数之和
题目15. 三数之和
参考官方题解使用排序双指针
这里也使用golang的对象完成处理
type threeSumData struct {nums []intn inttarget intres [][]intfirst intsecond intthird int
}func (t *threeSumData) threeSumWithFixC(target int) {// b取值得到了取c的值b在c的左侧c肯定大于b的c从后面往前去因为排序了所以正常情况bc targetfor t.second t.third {if t.nums[t.second]t.nums[t.third] target {break}t.third--}
}// 固定A值取BC target
func (t *threeSumData) threeSumWithFixB(target int) {t.third t.n - 1for second : t.first 1; second t.n; second {// 取一个b的值去掉重复的if second t.first1 t.nums[second] t.nums[second-1] {continue}t.second second// fmt.Printf(second %v\n, second)t.threeSumWithFixC(target)// 如果指针重合随着 b 后续的增加// 就不会有满足 abc0 并且 bc 的 c 了可以退出循环if t.second t.third {return}if t.nums[t.second]t.nums[t.third] target {t.res append(t.res, []int{t.nums[t.first], t.nums[t.second], t.nums[t.third]})}}
}func (t *threeSumData) threeSumWithFixA() {// 3 nums.length 3000// -10^5 nums[i] 10^5if t.n 2 {return}// 数组排序sort.Ints(t.nums)// 取a值for first : 0; first t.n; first {// 取一个a值如果当前值与上一个值一样则跳过if first 0 t.nums[first] t.nums[first-1] {continue}// 已经取了a值按照题目a b c target那么剩余 b c target - at.first firstremain : t.target - t.nums[first]// fmt.Printf(first %v\n, first)// a取值固定了取b值b在a值的后面t.threeSumWithFixB(remain)}
}func threeSum(nums []int) [][]int {data : threeSumData{nums: nums,n: len(nums),target: 0,res: make([][]int, 0),first: 0,second: 0,third: 0,}data.threeSumWithFixA()return data.res
}
六、四数之和
题目18. 四数之和
type fourSumData struct {nums []intn, target intres [][]intfirst, second, third, fourth int
}func (t *fourSumData) fourSumWithFixC() {nums : t.numsn : t.n// 双指针for left, right : t.second1, n-1; left right; {if sum : nums[t.first] nums[t.second] nums[left] nums[right]; sum t.target {t.res append(t.res, []int{nums[t.first], nums[t.second], nums[left], nums[right]})for left; left right nums[left] nums[left-1]; left {}for right--; left right nums[right] nums[right1]; right-- {}} else if sum t.target {left} else {right--}}
}func (t *fourSumData) fourSumWithFixB() {nums : t.numsn : t.nfor second : t.first 1; second n-2; second {// 连续的四个值和大于target时则四元组肯定不满足条件if nums[t.first]nums[second]nums[second1]nums[second2] t.target {return}// a、b、c 和 d 互不相同如果相同或者 AB最大的两个值不满足条件则以当前值为a值不会再有满足条件的四元组if second t.first1 nums[second] nums[second-1] || nums[t.first]nums[second]nums[n-2]nums[n-1] t.target {continue}t.second secondt.fourSumWithFixC()}
}func (t *fourSumData) fourSumWithFixA() {nums : t.numssort.Ints(t.nums)n : t.nfor first : 0; first n-3; first {// 连续的四个值和大于target时则四元组肯定不满足条件if nums[first]nums[first1]nums[first2]nums[first3] t.target {return}// a、b、c 和 d 互不相同如果相同或者A最大的三个值不满足条件则以当前值为a值不会再有满足条件的四元组if first 0 nums[first] nums[first-1] || nums[first]nums[n-3]nums[n-2]nums[n-1] t.target {continue}t.first firstt.fourSumWithFixB()}return
}func fourSum(nums []int, target int) [][]int {data : fourSumData{nums: nums,n: len(nums),target: target,res: make([][]int, 0),}data.fourSumWithFixA()return data.res
}
