双指针系列
题目的大致意思就是给一个数组, 要求你再数组中删除重复的项, 并返回删除后数组的长度。
思路
在这里想引入一个 过滤器 的思想, 思想其实很简单, 就是一个原数组通过 某种条件 过滤后得到一个新的数组。
算法模板:
for(){
if (){
## to do sth
}
}
var cnt = 0
for i,v :=range nums{
if (i == 0||nums[i] != nums[i-1]){
nums[cnt] = v
cnt ++
}
}
return cnt
题目的意思是说给定一个数组, 我们需要做的就是把数组中所有的0移动到数组的最后面。
思路
这道题的思想就是用到了过滤器的思想, 条件就是遇到0就进行后移, 本题第二个for循环实际上是为了将最后不是0的元素填充为0, 因为如果不这样做的话, 数组最终的结果是
var cnt = 0
for _, v := range nums {
if v != 0 {
nums[cnt] = v
cnt++
}
}
for cnt < len(nums) {
nums[cnt] = 0
cnt++
}
题目的意思是说有两个数组A, B, 分别为a, b, 要求我们把两个数组按照非递减的顺序合并为一个数组。
思路1
直接声明一个新的数组res, 并最终将res数组中的所有值填充到nums1中即可。
var res []int
var i = 0
var j = 0
for (i < m || j < n ){
if (j >= n ||( i < m && nums1[i] < nums2[j])){
res = append(res,nums1[i])
i++
}else{
res = append(res,nums2[j])
j++
}
}
for i,v :=range res {
nums1[i] = v
}
思路2
因为思路1是在声明了一个新的数组res, 有没有一种可能不用声明新的数组，直接在原数组上利用前后2个指针(即就是双指针的思想)呢, 这里可以思考一下为什么要用前后2个指针, 而不是2个指针都从前往后走，我们举一个例子
i
1,2,3,0,0,0nums1
2,5,6 nums2
j
## 如果双指针采取正着走的方式,当i,j处于此位置时，情况就会变成
i
1,2,2,0,0,0 nums1
2,5,6 nums2
j
## 是的,3就会被我们给“弄丢”,我们再来看nums1从3后面的都是0,我们并不在乎0是否弄丢,因此我们可以新声明一个cnt指针让,并且让i,j,cnt从后往前移动,那么情况就会变成这样
i cnt
1,2,3,0,0,0 nums1 ## 6大于3所以会变成这样
2,5,6 nums2
j
i cnt
1,2,3,0,0,6 nums1 ## 5大于3所以会变成这样
2,5,6 nums2
j
i cnt
1,2,3,0,5,6 nums1 ## 3大于2所以会变成这样
2,5,6 nums2
j
i cnt
1,2,3,3,5,6 nums1 ## 2==2直接拷贝,所以会变成这样
2,5,6 nums2
j
i cnt
1,2,2,3,5,6 nums1 ## 2==2直接拷贝,所以会变成这样
2,5,6 nums2 ##j走到头,结束
j
所以思路2的代码如下
var i = m - 1
var j = n - 1
var cnt = m + n -1
for (i>= 0 || j >= 0){
if (j < 0||(i >= 0 && nums1[i] > nums2[j])) {
nums1[cnt] = nums1[i]
i--
}else{
nums1[cnt] = nums2[j]
j--
}
cnt--
}
题目的意思是说给定一个数组nums和一个整数k,如果某个连续的子数组恰好有符合k个数的奇数数字，则我们就认为该数组为优美子数组，然后返回优美子数组的个数。
思路
## 原数组[1,1,2,1,1] ->%2后变为
## [1,1,0,1,1] nums[0]~nums[3]的和为3(k) nums[1]~nums[4]的和为3(k),即找到了我们要的子数组
## 即通过%2将找k个奇数的子数组->找和为k的子数组->s[i]-s[j] = k
## s[i] 代表的是数组nums[0]~nums[i]的和
## %2-> [1,1,0,1,1]
## s[i]-> [1,2,2,3,4] ->这里需要额外添加一个0
## [0,1,2,2,3,4]
## 4-1=3则代表找到了[1,0,1,1]这个子数组,3-0=3则代表找到了[1,1,0,1]这个子数组
## 由此本题变为了找s[j]-s[i] = k 即两数之和的问题
## 这里声明还要额外声明一个cnt用来统计sum中每个元素出现的次数,比如
## sum->[0,1,2,2,3,4]
## 则cnt-> [0:1,
## 1:1,
## 2:2,
## 3:1,
## 4:1]
ans:=0
sum:=make([]int,len(nums)+1)
sum[0] = 0
for i,v:=range nums{
sum[i+1] = sum[i] + (v%2)
}
count:=make([]int,len(sum))
for _,s:=range sum{
if s - k >= 0 {
ans += count[s-k]
}
count[s]++
}
return ans
题目的意思一个数组中有若干个元素,让你求最大子数组的和,并将和返回。
思路
假设nums[0]为最大，从nums[1]开始循环，如果nums[i]+nums[i-1]>nums[i],就证明是连续增的,直接进行累加,如果发现有一个nums[i]大于已经存在的最大的max,则将这个nums[i]赋值给max，即max永远是最大的,最后返回max即可
max:=nums[0]
for i:= 1; i < len(nums); i++{
if nums[i]+nums[i-1]>nums[i]{
nums[i]+=nums[i-1]
}
if nums[i]>max{
max = nums[i]
}
}
return max