package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{
		-1, 0, 1, 2, -1, -4,
	}

	results := threeSum(nums)
	fmt.Println("results", results)
}

// 暴力求解
/*
 */
func threeSum(nums []int) [][]int {
	ans := [][]int{}
	sort.Ints(nums)
	n := len(nums)

	// 枚举a
	for first := range nums {
		if first > 0 && nums[first] == nums[first-1] {
			continue
		}
		// c 对应的指针初始指向数组的最右端
		third := n - 1
		target := -1 * nums[first]
		// 枚举B
		for second := first + 1; second < n; second++ {
			// 需要和上一次枚举的数不同threeSum
			if second > first+1 && nums[second] == nums[second-1] {
				continue
			}
			// 需要保证 b 的指针在 c 的指针的左侧
			for second < third && nums[second]+nums[third] > target {
				third--
			}

			// 如果指针重合，随着 b 后续的增加
			// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
			if second == third {
				break
			}
			if nums[second]+nums[third] == target {
				ans = append(ans, []int{nums[first], nums[second], nums[third]})
			}

		}

	}

	return ans
}

package main

import (
	"fmt"
)

func main() {
	nums := []int{
		3, 2, 4,
	}
	target := 6

	results := twoSum(nums, target)
	fmt.Println("results", results)

	results2 := twoSum2(nums, target)
	fmt.Println("results2", results2)
}

// 暴力求解
func twoSum(nums []int, target int) []int {
	returnVal := []int{}
	for k1, v1 := range nums {
		diff := target - v1
		for k2, v2 := range nums {
			if diff == v2 && k2 != k1 {
				returnVal = append(returnVal, k2)
			}
		}
	}
	return returnVal
}

// 利用哈希 map
func twoSum2(nums []int, target int) []int {
	hashTable := map[int]int{}
	for i, x := range nums {
		p, ok := hashTable[target-x]
		if ok {
			return []int{p, i}
		}
		hashTable[x] = i
	}
	return nil
}

package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	strs := []string{"eat", "tea", "tan", "ate", "nat", "bat"}

	results := groupAnagrams(strs)
	fmt.Println("results", results)
}

// 暴力求解
func groupAnagrams(strs []string) [][]string {
	hasMap := map[string][]string{}
	for _, v := range strs {
		splitStr := strings.Split(v, "")
		sort.Strings(splitStr)
		sortStr := strings.Join(splitStr, "")
		hasMap[sortStr] = append(hasMap[sortStr], v)
	}

	returnVal := [][]string{}

	for _, v := range hasMap {
		returnVal = append(returnVal, v)
	}

	return returnVal
}

package main

import (
	"fmt"
)

func main() {
	nums := []int{
		0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1,
	}

	results := trap(nums)
	fmt.Println("results", results)
}

// 暴力求解
/*
 */

func trap(height []int) int {
	return 0
}

package main

import (
	"fmt"
	"sort"
)

func main() {
	nums := []int{
		0, 1, 1, 2,
	}

	results := longestConsecutive(nums)
	fmt.Println("results", results)

	results2 := longestConsecutive2(nums)
	fmt.Println("results2", results2)
}

// 暴力求解
/*
下一个减去上一个，结果为1则判定为有效
*/
func longestConsecutive(nums []int) int {
	// 去重
	hasMap := map[int]bool{}
	newArr := []int{}
	for _, v := range nums {
		if !hasMap[v] {
			hasMap[v] = true
			newArr = append(newArr, v)
		}
	}
	// 排序
	sort.Ints(newArr)

	// fmt.Println("newArr", newArr)

	lineArr := []int{}
	// result := [][]int{}

	max := 0

	if len(newArr) == 1 {
		return 1
	}

	for idx, item := range newArr {
		nextIdx := idx + 1
		if nextIdx > len(newArr)-1 {
			nextIdx = 0
		}
		now := item
		next := newArr[nextIdx]

		if next-now == 0 {
			continue
		}

		if next-now == 1 {
			lineArr = append(lineArr, item)
		} else {
			lineArr = append(lineArr, item)
			// result = append(result, lineArr)
			if len(lineArr) > max {
				max = len(lineArr)
			}
			lineArr = []int{}
		}

	}

	// fmt.Println("result", result)

	return max
}

// 利用哈希表
/*
将数组映射成哈希表
然后在哈希表中找-1的数字是否存在
*/
func longestConsecutive2(nums []int) int {
	numSet := map[int]bool{}
	for _, num := range nums {
		numSet[num] = true
	}
	longestStreak := 0
	for num := range numSet {
		if !numSet[num-1] {
			currentNum := num
			currentStreak := 1
			for numSet[currentNum+1] {
				currentNum++
				currentStreak++
			}
			if longestStreak < currentStreak {
				longestStreak = currentStreak
			}
		}
	}
	return longestStreak
}

package main

import (
	"fmt"
)

func main() {
	nums := []int{
		1, 8, 6, 2, 5, 4, 8, 3, 7,
	}
	results := maxArea(nums)
	fmt.Println("results", results)
}

// 暴力求解
/*
计算最大容积
容积的公式为 底*高

底 = 当前下标和未来下标的差
高 = 二者之间最大值
*/
func maxArea(height []int) int {
	res := 0             // 最大面积
	l := 0               // 最左边
	r := len(height) - 1 // 最右边

	for l < r {

		y := 0
		x := r - l

		if height[l] < height[r] {
			y = height[l]
			l++
		} else {
			y = height[r]
			r--
		}
		are := y * x
		if are > res {
			res = are
		}
	}

	return res
}

package main

import (
	"fmt"
)

func main() {
	nums := []int{1, 2, 0, 3, 4, 0, 1, 0, 5, 0}
	fmt.Println("nums", nums)
	moveZeroes(nums)
	fmt.Println("nums", nums)

	nums2 := []int{0, 3, 4, 0, 1, 0, 5, 0}
	fmt.Println("nums2", nums2)
	moveZeroes2(nums2)
	fmt.Println("nums2", nums2)
}

// 暴力求解
/*
标记非 0 的值，然后进行替换
*/
func moveZeroes(nums []int) {
	notZero := []int{}
	for _, item := range nums {
		if item != 0 {
			notZero = append(notZero, item)
		}
	}

	for idx := range nums {
		if idx <= len(notZero)-1 {
			nums[idx] = notZero[idx]
		} else {
			nums[idx] = 0
		}
	}
}

// 非0值移动

func moveZeroes2(nums []int) {
	j := 0
	for _, v := range nums {
		if v != 0 {
			nums[j] = v
			j++
		}
	}
	// 将其余值设为0
	for i := j; i < len(nums); i++ {
		nums[i] = 0
	}
}