【golang 必备算法】数组篇

704. 二分查找

注意边界问题

func search(nums []int, target int) int {

    r,l,mid:=0,len(nums)-1,(len(nums)-1)/2
    for l>=r{
        mid = (r+l)/2
        if nums[mid]==target{
            return mid
        }else if nums[mid]>target{
            l=l-1
        }else{
            r=r+1
        }
    }

    return -1
}

27. 移除元素

解法一：

func removeElement(nums []int, val int) int {
    res:=0
    for _,v:=range nums{
     if v!=val{
         nums[res]=v
         res++
     }
    }
    return res
}

解法二（双指针）：

func removeElement(nums []int, val int) int {

i:=0
j:=0

for j<len(nums){
    if nums[j]==val{
        j++
    }else{
        nums[i]=nums[j]
        i++
        j++
    }
}
return len(nums)-(j-i)
}

977.有序数组的平方

双指针
创建一个和原来数组一样大小的数组res
比较头指针和尾指针指向数的平方和，将大的数存在res[k--]中

func sortedSquares(nums []int) []int {
    l:=len(nums)
    res:=make([]int,l)
    i,j:=0,l-1
    k:=j
    for i<=j{
        if nums[i]*nums[i]>=nums[j]*nums[j]{
            res[k]= nums[i]*nums[i]
            i++
        }else{
              res[k]= nums[j]*nums[j]
              j--
        }
        k--
    }
    return res
}

209.长度最小的子数组

滑动窗口

func minSubArrayLen(s int, nums []int) int {
sum:=0
start:=0
end:=0
a:=math.MaxInt32

for end<len(nums){
    sum=sum+nums[end]
        for sum>=s{
            sum=sum-nums[start]
             a=min(a,end-start+1)
            start++
        }
        end++
}
if a==math.MaxInt32{
    return 0
}else{
    return a
}
}
func min(x int,y int)int{
    if x>y{
        return y
    }else{
        return x
    }
}

59. 螺旋矩阵 II

func generateMatrix(n int) [][]int {

arr:=make([][]int,n)
for k,_:=range arr{
    arr[k]=make([]int,n)
}
 top, bottom := 0, n-1
 left, right := 0, n-1
m:=1

for m<=n*n{
    for i:=left;i<=right;i++{
        arr[top][i]=m
        m++
    }
    top++

    for i:=top;i<=bottom;i++{
        arr[i][right]=m
        m++
    } 
    right--

    for i:=right;i>=left;i--{
        arr[bottom][i]=m
        m++
    }
    bottom--

    for i:=bottom;i>=top;i--{
        arr[i][left]=m
        m++
    }
    left++
}
return arr

}