数组

两个数组的交集

349

题目大意：题目要求找到两个数组的交集，如果交集元素同一个数字出现多次，只输出一次。

思路：把num1写进一个map，此map的键为num1的数字值，然后遍历num2，判断数字是否在map中存在，如果存在，在map中删除，将数字加入res中。

func intersection(nums1 []int, nums2 []int) []int {
    m := map[int]bool{}
    var res []int
    for _, v := range nums1 {
        m[v] = true
    }
    for _, v := range nums2 {
        if m[v]{
            delete(m,v)
            res = append(res,v)
        }
    }
    return res
}

350

题目大意：题目要求找两个数组的交集，并且保留相同元素。

思路：将num1写进一个map，键为num1数组的值，值为出现次数，之后遍历num2，检查其中的元素是否在map中出现，如果出现，则将该元素加入结果res中，并将map中该元素出现次数减一。

func intersect(nums1 []int, nums2 []int) []int {
    m := map[int]int{}
    var res []int
    for _, v := range nums1 {
        m[v]++
    }
    for _, v := range nums2 {
        if m[v]>0{
            res =append(res,v)
            m[v]--
        }
    }
    return res
}

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？

思路：利用双指针，设定两个为0的指针，比较两个指针的元素是否相等，如果相等，将两个指针一起向后移动，将相等元素放入一个空白数组。如果不相等，将元素值小的一个指针向后移动，继续进行判断，直到任意一个数组终止。

func intersect(nums1 []int, nums2 []int) []int {
    i, j, k := 0, 0, 0
    var nums []int
    sort.Ints(nums1)
    sort.Ints(nums2)
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] > nums2[j] {
            j++
        } else if nums1[i] < nums2[j] {
            i++
        } else {
            nums[k] = nums1[i]
            i++
            j++
            k++
        }
    }
    return nums[:k]
}

最长的公共前缀

14

题目大意：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，则返回””

思路：选定一个基准元素，将基准元素与后面的元素进行比较，不断更新基准元素，直到和所有元素都满足最长公共前缀的条件。

这里选定数组中第一个元素为基准元素，当pre在v中出现的位置为0时，可以认定pre就是v的最长前缀（如flower和flow比较）。当pre在v中出现的位置不为0时，可以认定此时的pre不为最长公共前缀，这时就可以将pre的最后一个字母截掉，再次与v进行比较，直到满足string.Index(v,pre) == 0

最后处理一下临界条件。给定数组为空，说明没用公共前缀。

用到strings包下index方法
func Index(s, sep string) int
子串sep在字符串s中第一次出现的位置，不存在则返回-1。

func longestCommonPrefix(strs []string) string {
    if len(strs)<1{
        return ""
    }
    pre := strs[0]
    for _, v := range strs {
        for strings.Index(v,pre)!=0 {
            if len(pre)==0{
                return ""
            }
            pre = pre[:len(pre)-1]
        }
    }
    return pre
}

买卖股票的最佳时机

121

题目大意：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

思路：找出最低价和最高价，差价即为最大收益。初始化第一天的价格为买入价，遍历数组，更新最低价和最大利润。

func maxProfit(prices []int) int {
    buyPrice := prices[0]
    maxProfit :=0
    for i := 1; i <len(prices); i++ {
        if prices[i]<buyPrice {
            buyPrice = prices[i]
        }else {
            profit := prices[i]-buyPrice
            if profit>maxProfit {
                maxProfit = profit
            }
        }
    }
    return maxProfit
}

122

题目大意：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：获取最大收益即为跌了就买入，涨到顶峰就卖出。

当后一天的价格大于前一天时，两者价格差即为收益。

func maxProfit(prices []int) int {
    profit := 0
    for i := 0; i < len(prices)-1; i++ {
        if prices[i+1]>prices[i] {
            profit += prices[i+1]-prices[i]
        }
    }
    return profit
}

123

题目大意：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

思路：动态规划，在同一天会有四种状态：

进行过一次买操作；
进行了一次买操作和一次卖操作，即完成了一笔交易；
在完成了一笔交易的前提下，进行了第二次买操作；
完成了全部两笔交易。

buy1为第一次买入的价格（取当前价格和之前第一次买入价格的较小值），sell1为第一次卖出时的利润（取当前价格减去第一次买入价格和之前第一次卖出利润的较大值），buy2为第二次买入的价格（取当前价格减去之前第一次卖出利润和之前第二次买入价格的较小值），sell2为第二次卖出时的利润（取当前价格减去之前第二次买入价格和之前第二次卖出利润的较大值）。

func maxProfit(prices []int) int {
    if len(prices)==0 {
        return 0
    }
    buy1 := prices[0]
    sell1 := 0
    buy2 := prices[0]
    sell2 := 0
    for i := 1; i < len(prices); i++ {
        buy1 = min(buy1, prices[i])
        sell1 = max(sell1,prices[i]-buy1)
        buy2 = min(buy2,prices[i]-sell1)
        sell2 = max(sell2,prices[i]-buy2)
    }
    return sell2
}

func max(a,b int)int  {
    if a>b{
        return a
    }
    return b
}
func min(a,b int)int  {
    if a<b {
        return a
    }
    return b
}

旋转数组

189

题目大意：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路：翻转后，末尾 k mod n 个元素移动至了数组头部，剩下的元素右移 k mod n 个位置至最尾部。

解法一：将下标为i的元素移动到(i+k) mod n 的位置，再将剩下的元素拷贝回来即可。

func rotate(nums []int, k int) {
    ints := make([]int, len(nums))
    for i, v := range nums {
        ints[(i+k)%len(nums)] = v
    }
    copy(nums,ints)
}

解法二：将数组元素直接翻转，然后以k mod n为分界点，前后分别翻转

func rotate(nums []int, k int) {
    re(nums)
    re(nums[:k%len(nums)])
    re(nums[k%len(nums):])
}

func re(arr []int)  {
    for i := 0; i < len(arr)/2; i++ {
        arr[i],arr[len(arr)-i-1] = arr[len(arr)-i-1],arr[i]
    }
}

原地删除

27

题目大意：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

思路：

解法一：遍历整个数组，当前值等于目标值时，移除当前值，不等于时，i++。注意：这里将索引为i的元素删除，是在原数组上操作的，原来索引为i+1的元素会变为i，所以在删除时，不能执行i++操作。

func removeElement(nums []int, val int) int {
    for i := 0; i < len(nums); {
        if nums[i] ==val {
            nums = append(nums[:i],nums[i+1:]...)
        }else {
            i++
        }
    }
    return len(nums)
}

解法二：利用双指针，将不等于目标值的元素移动到数组前端，更新指针i,最后返回i的值即为新数组的长度。这里删除的元素实际上是没被删除的，是被移动到了数组后侧，被截取掉了。

func removeElement(nums []int, val int) int {
    i := 0
    for j := 0; j < len(nums); j++ {
        if nums[j] != val{
            nums[i] = nums[j]
            i++
        }
    }
    return i
}

26

题目大意：给定一个有序数组 nums，对数组中的元素进行去重，使得原数组中的每个元素只有一个。最后返回去重以后数组的长度值。

思路：

解法一：遍历数组，当i+1值等于i对应的值时，删除第i+1元素。

func removeDuplicates(nums []int) int {
    for i := 0; i <len(nums)-1; {
        if nums[i] == nums[i+1]{
            nums = append(nums[:i+1],nums[i+2:]...)
        }else {
            i++
        }
    }
    return len(nums)
}

解法二：双指针，遍历数组，当前元素不等于后一个元素时，将后一元素移动到前面。这里也是实际并未删除

func removeDuplicates(nums []int) int {
    i := 1
    for j := 0; j < len(nums)-1; j++ {
        if nums[j] != nums[j+1]{
            nums[i] = nums[j+1]
            i++
        }
    }
    return i
}

283

题目大意：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

思路：

解法一：遍历数组，将为零元素删除，j记录删除的个数，最后将删除的零添加到数组后端。

func moveZeroes(nums []int) {
    j :=0
    for i := 0; i < len(nums)-1; {
        if nums[i] == 0{
            nums = append(nums[:i],nums[i+1:]...)
            j++
        }else {
            i++
        }
    }
    zeros := make([]int,j)
    nums = append(nums, zeros...)
}

解法二：双指针，i遍历数组，j记录非零元素要放置的位置，遍历数组时，当前元素不为零，则将其与指针j指向的位置进行交换，并更新j指针。

func moveZeroes(nums []int) {
    j := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] != 0{
            if  i != j {
                nums[i], nums[j] = nums[j], nums[i]
            }
            j++
        }
    }
}

80

题目大意：给你一个有序数组 nums ，请你** 原地** 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

思路：双指针，将出现次数超过两次的元素移动到数组的前面，并更新指针 i。最后，函数返回指针 i 的值，即为删除重复元素后的新数组的长度。

func removeDuplicates(nums []int) int {
    if len(nums) <= 2 {
        return len(nums)
    }
    i := 2
    for j := 2; j < len(nums); j++ {
        if nums[j] != nums[i-2] {
            nums[i] = nums[j]
            i++
        }
    }
    return i
}

加一

66

题目大意：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

思路：从数组最后一位开始遍历，如果当前位小于9，直接加一返回结果，如果当前位为9，将该位设置为0，并进位。如果所有位都进位了，就在数组开头插入一个1。

func plusOne(digits []int) []int {
    for i := len(digits)-1; i >=0 ; i-- {
        if digits[i] < 9 {
            digits[i]++
            return digits
        }
        digits[i] = 0
    }
    return append([]int{1},digits...)
}

两数之和

1

题目大意：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

思路：暴力题解，遍历每个元素 i，并查找是否存在一个值与 target - i 相等的目标元素。

func twoSum(nums []int, target int) []int {
    for i, v:= range nums {
        for k:=i+1;k<len(nums);k++{
            if target-v==nums[k] {
                return []int{i,k}
            }
        }
    }
    return nil
}

使用哈希表

func twoSum(nums []int, target int) []int {
    m:= make(map[int]int)
    for i, num := range nums {
        if index,found := m[target-num] ;found{
            return []int{index,i}
        }
        m[num]=i
    }
    return nil
}

三数之和

15

题目大意：给定一个数组，要求在这个数组中找出 3 个数之和为 0 的所有组合。

思路：使用排序以及双指针解决，首先对数组进行排序，固定一个数，使用双指针来查找另外两个数。排序后，如果固定数本身大于0，那么三数之和必定不为0。移动左右指针，如果和大于0，说明右指针太大，需要左移，如果和小于0，说明左指针太小，需要右移。接下来就是处理重复值的情况，对于固定值以及左右指针都需要做重复值处理。

func threeSum(nums []int) [][]int {
    var result [][]int
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue  //避免重复固定值
        }
        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum == 0 {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                left++
                right--
                for left < right && nums[left] == nums[left-1] {
                    left++  //避免重复左指针
                }
                for left < right && nums[right] == nums[right+1] {
                    right--  //避免重复右指针
                }
            } else if sum < 0 {
                left++
            } else {
                right--
            }
        }
    }
    return result
}

那么四数之和也就差不大多，固定两个数，同样使用双指针。