力扣100热题：两、三、四数之和，哈希+数组+双指针+排序

目录

一、两数之和

二、两数之和 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从后面往前去，因为排序了，所以正常情况，b+c>= targetfor t.second < t.third {if t.nums[t.second]+t.nums[t.third] <= target {break}t.third--}
}// 固定A值，取B+C = target
func (t *threeSumData) threeSumWithFixB(target int) {t.third = t.n - 1for second := t.first + 1; second < t.n; second++ {// 取一个b的值，去掉重复的if second > t.first+1 && t.nums[second] == t.nums[second-1] {continue}t.second = second// fmt.Printf("second %v\n", second)t.threeSumWithFixC(target)// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 b<c 的 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.second+1, 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[right+1]; 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[second+1]+nums[second+2] > t.target {return}// a、b、c 和 d 互不相同，如果相同，或者 A+B+最大的两个值，不满足条件，则以当前值为a值，不会再有满足条件的四元组if second > t.first+1 && 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[first+1]+nums[first+2]+nums[first+3] > 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
}