leetcode-双指针

409.最长回文子串

代码：

func longestPalindrome(s string) int {
    var pair := make(map[byte]int)
    for i:=0;i<len(s);i++{
        pair[s[i]]++
    }
    var sum int
    flag := false
    for _,v := range(pair){
        if v % 2 != 0{
            flag = true
            v = v - 1
        }
        sum += v
    }
    if flag {
        sum ++ 
    }
    return sum
}

思路：

1. 只需返回回文串长度，只要是字符出现的次数为偶数就直接相加，如果有为奇数的，则减1相加，并把标志位置true,最后总的sum加一
2. 没用到双指针，也没看到题解用双指针，不知道双指针是怎么实现的

125.验证回文串

代码：

func isPalindrome(s string) bool {
    var a string
    for i:=0;i<len(s);i++{
        if isANum(s[i]){
            a += string(s[i])
        }
    }
    a = strings.ToUpper(a)
    for i,j:=0,len(a)-1;i<j;i++{
        if a[i] != a[j]{
            return false
        }
        j--
    }
    return true
}

func isANum(s byte)bool{
    return (s >='0' && s <= '9') || (s >= 'A' && s <= 'Z') || (s >='a' && s <='z')
}

思路：

1. 在原字符串上一边遍历一边改变长度不是个好办法，情愿新申请一个变量
2. 预处理字符串后，使用双指针头尾结合判断
3. A的ASCII码为65，Z的ASCII码为90，a的ASCII码为97，z的ASCII码为122

5.最长回文子串

代码：

func longestPalindrome(s string) string {
    maxLen := ""
    for i:=0;i<len(s);i++{
        temLen := ""
        for left,right:=i,i;left >=0 && right <len(s);left--{
            if s[left] != s[right]{
                break
            }
            temLen = s[left:right+1]
            if len(temLen) > len(maxLen){
                maxLen = temLen
            } 
            right++
        }

        temLen = ""    
        for left,right:=i,i+1;left >=0 && right <len(s);left--{
            if s[left] != s[right]{
                break
            }
            temLen = s[left:right+1]
            if len(temLen) > len(maxLen){
                maxLen = temLen
            } 
            right++
        }
    }
    return maxLen
}

思路：

1. 中心扩散法，从第一个位置开始，两个指针分别向两边扩散，判断是否相等，保存最长的字符串
2. 有两种情况，一种为偶偶，另种为偶奇偶。扩散的方式不同，需要两种情况

1.两数之和

代码：

func twoSum(nums []int, target int) []int {
   pair := make(map[int]int)
   for k,v := range(nums){
       if ret,ok := pair[target-v];ok{
           return []int{ret,k}
       }
       pair[v] = k
   }
   return []int{}
}

思路：

1. 使用target—v来作为查找判断，这个key是否在map里。
2. index作为map的value，这样直接定位到在数组中的序号

15.三数之和

代码：

import "sort"

func threeSum(nums []int) [][]int {
    ret := [][]int{}
    sort.Ints(nums)
    for i:=0;i<len(nums);i++{
        if i > 0 && nums[i] == nums[i-1]{
            continue
        } 
        k := len(nums)-1
        target := -1 * nums[i]
        for j:=i+1;j<len(nums);j++{
            if j > i+1 && nums[j] == nums[j-1]{
                continue
            }
            for j < k && nums[k] + nums[j] > target{
                k--
            }

            if k == j{
                break
            }
            if nums[k] + nums[j] == target{
                ret = append(ret,[]int{nums[i],nums[j],nums[k]})
            }
        }
    }
    return ret
}

思路：

1. 先排序，排完一切好说
2. 如果两个数是一样的，就跳过
3. 利用递增的特性，第三圈的时候，把指针移到小于的情况
4. 直接判断是的话就append
5. 当j递增的时候，k在回到第三步