算法.md

算法

1. 双指针

1. 对撞指针：两个指针相向而行，对撞而来。
   • 01两数之和（https://leetcode-cn.com/problems/two-sum/）
   • 15三数之和（https://leetcode-cn.com/problems/3sum/）
   • 16最接近三数之和（https://leetcode-cn.com/problems/3sum-closest/）
   • 125验证回文串（https://leetcode-cn.com/problems/valid-palindrome/）
   • 11盛最多水的面积（https://leetcode-cn.com/problems/container-with-most-water/）
2. 滑动窗口：由两个指针形成一个可变化的窗口。
3. 快慢指针：一个指针跑得快，一个指针跑得慢。
4. 双指针:就是用到两个指针了，不属于上面的三种情况。

20220109对撞指针两个实例

1.twoSum

package main

import "fmt"

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

//1.两个for
//2.hashtable
//3.two pointer
func twoSum(nums []int, target int) []int {
	left, right := 0, len(nums)-1
	for left < right {
		if nums[left]+nums[right] == target {
			return []int{left, right}
		} else if nums[left]+nums[right] > target {
			right--
		} else {
			left++
		}
	}
	return nil
}

2.threeSum

package main

import (
	"fmt"
	"sort"
)

//给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//满足要求的三元组集合为：
//[
//[-1, 0, 1],
//[-1, -1, 2]
//]

//a+b+c=0
//0-a=b+c
//[-4,-1,-1,0,1,2]
//target=0-(-4)=4  [-1,-1,0,1,2] 是否有两数相加等于4。
//target=0-(-1)=1  [-1,0,1,2]是否有两数相加等于1。
//主体思想：不用暴力的解法 。想办法 把这道题转换成two-sum的题去做。
//第一步，排序，按从小到大排序。
//取第i个元素，以0-nums[i]为target,在后面的数里面去找看是否有两个数相加等于target。
//条件：len(nums)-2
//去重。
//1.target的去重。
//2.left和right的去重。
func main() {
	// var nums []int = []int{-1, 0, 1, 2, -1, -4}
	var nums []int = []int{-1, 0, 0, 0, 0, 1, 1, 1, 1}
	fmt.Println(threeSum(nums))
}

func threeSum(nums []int) [][]int {
	var res [][]int = [][]int{}
	sort.Ints(nums)
	for i := 0; i < len(nums)-2; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		target := 0 - nums[i]
		left, right := i+1, len(nums)-1
		for left < right {
			if nums[left]+nums[right] == target {
				r := []int{nums[i], nums[left], nums[right]}
				res = append(res, r)
				left++
				for nums[left] == nums[left-1] {
					left++
				}
				right--
				for nums[right] == nums[right+1] {
					right--
				}
			} else if nums[left]+nums[right] > target {
				right--
			} else {
				left++
			}
		}
	}
	return res
}