双指针
#LeetCode#算法#双指针 2023-12-31

双指针

题目

相向双指针

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

15. 三数之和 - 力扣（LeetCode）

16. 最接近的三数之和 - 力扣（LeetCode）

18. 四数之和 - 力扣（LeetCode）

611. 有效三角形的个数 - 力扣（LeetCode）

2824. 统计和小于目标的下标对数目 - 力扣（LeetCode）

11. 盛最多水的容器 - 力扣（LeetCode）

同向双指针（滑动窗口）

209. 长度最小的子数组 - 力扣（LeetCode）

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

3. 无重复字符的最长子串 - 力扣（LeetCode）

1004. 最大连续1的个数 III - 力扣（LeetCode）

1234. 替换子串得到平衡字符串 - 力扣（LeetCode）

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

LeetCode 167

思路

维护一个左右指针，当两数之和小于 target 时，左指针移动（左边再和右指针相加的数不可能等于 target 了，只能是小于）。当大于时，右指针移动（右边再和左指针相加的数不可能等于 target 了，只能是大于）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func twoSum(numbers []int, target int) []int {
    var left, right int = 0, len(numbers) - 1 // 初始化左右指针
    var res []int // 初始化结果数组
    for left < right{
        sum := numbers[left] + numbers[right]
        if sum == target{
            res = append(res, []int{left+1,right+1}...)
            left++
            right--
        }else if sum < target{
            left++
        }else{
            right--
        }
    }
    return res
}

LeetCode 15

思路

主要的不同在于，遇到相同的元素，我们需要跳过它。其余和双指针差不多。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func threeSum(nums []int) [][]int {
    // 先排序
    sort.Ints(nums)
    var ans [][]int
    for i := 0; i < len(nums) - 2; i++{
        var now = nums[i]
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }

        // 开始双指针
        j := i + 1
        k := len(nums) - 1
        for j < k{
            sum := now + nums[j] + nums[k]
            if sum == 0{
                ans = append(ans, []int{now, nums[j], nums[k]})
                j++
                // 遇到相同的就跳过
                for j < k && nums[j] == nums[j-1]{
                    j++
                }
                k--
                // 遇到相同的就跳过
                for j < k && nums[k] == nums[k+1]{
                    k--
                }
            }else if sum < 0{
                j++
            }else{
                k--
            }
        }
    }
    return ans
}

LeetCode 16

思路

和三数之和差不多，注意条件就行

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func threeSumClosest(nums []int, target int) int {
    // 先排序
    sort.Ints(nums)
    var ans int = 100001
    for i := 0; i < len(nums) - 2; i++{
        var now = nums[i]
        if i > 0 && nums[i] == nums[i-1]{
            continue
        }

        // 开始双指针
        j := i + 1
        k := len(nums) - 1
        for j < k{
            poor := now + nums[j] + nums[k] - target
            if poor == 0{
                return target
            }else if poor < 0{
                // 搞到正数会不会好一点
                j++
            }else{
                // 小一点会不会更好
                k--
            }

            if abs(poor) < abs(ans - target){
                ans = poor + target
            }
        }
    }
    return ans
}

func abs(i int) int{
    if i < 0{
        return -i
    }
    return i
}

LeetCode 18

思路

和三数之和差不多，遍历 i 时（x），遍历 j（y），然后维护一个双指针（z 与 k）。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func fourSum(nums []int, target int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
    for i := 0; i < n - 3; i++{
        x := nums[i]
        // 重复数字跳过
        if i > 0 && x == nums[i-1]{
            continue
        }

        for j := i + 1; j < n  - 2; j++{
            y := nums[j]
            // 重复数字跳过
            if j > i + 1 && y == nums[j-1]{
                continue
            }
			
            // 双指针
            z := j + 1
            k := n - 1
            for z < k{
                sum := x + y + nums[z] + nums[k]
                if sum == target{
                    ans = append(ans, []int{x, y, nums[z], nums[k]})
                    
                    // 跳过重复数字
                    z++
                    for z < k && nums[z] == nums[z-1]{z++}
                    k--
                    for z < k && nums[k] == nums[k+1]{k--}
                }else if sum < target{
                    z++
                }else{
                    k--
                }
            }
        }
    }
    return ans
}

LeetCode 611

思路

三角形边要满足的条件是：

  1. 两边之和大于第三边
  2. 两边之差小于第三边

即：

  1. a + b > c
  2. a + c > b
  3. b + c > a

当 a b c 满足 1 < a < b < c 时，只需要 a + b > c，那么这三条边就可以构成一个三角形。

那么怎么运用到双指针的知识呢？

我们可以从第三个元素开始遍历边数组（第三条边），即把当前遍历到的元素 nums[i] 当成第三条边。每次遍历执行以下操作：

  1. 初始化双指针，左指针 j 从 0 开始，右指针 k 从 i - 1 开始。

  2. 当 nums[j] + nums[k] > nums[i] 时（两边之和大于第三边）：

    1. 数组是按照递增顺序排序的，如果上述条件成立，那么 j++ 直到 j = k - 1 式子nums[j] + nums[k] > nums[i] 都是成立的。所以使 ans += k - j，然后 k–。
    2. 否则 j++ 继续寻找合适的边
    3. j < k 时停止查找

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func triangleNumber(nums []int) int {
    sort.Ints(nums)
    var ans int
    for i := 2; i < len(nums); i++{
        j := 0
        k := i - 1
        for j < k{
            if nums[j] + nums[k] > nums[i]{
                // k - j 都是符合条件的
                ans += k - j
                k--
            }else{
                j++
            }
        }
    }
    return ans
}

LeetCode 2824

思路

唯一要注意的就是找到符合条件的 left right 时，ans 要加上 right - left 的值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func countPairs(nums []int, target int) int {
    sort.Ints(nums)
    var ans int
    var left, right = 0, len(nums) - 1
    for left < right{
        sum := nums[left] + nums[right]
        if sum >= target{
            // 太大了
            right--
        }else{
            ans += right - left
            left++
        }
    }
    return ans
}

LeetCode 11

思路

这题有个很关键的点在于：最低的边决定面积的大小（木桶效应）。

面积等于： min(h1,h2) * (right - left)

通过上述式子，我们移动 right 和 left 时，(right - left) 都会减小 1，仅考虑这个因素，那么它们谁往中间移动都是无关紧要的。影响面积大小的因素就是 min(h1, h2)。如果：

  1. 移动低的边，那么面积可能减小或者增大。
  2. 移动高的边，面积一定会变小。（因为 min(h1,h2) 的短板要么更小，要么不变）

所以选择移动低的边，直到双指针相撞。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func maxArea(height []int) int {
    var left, right = 0, len(height) - 1
    var ans int
    for left < right{
        w := right - left
        h := min(height[left], height[right])
        temp := w * h
        ans = max(ans, temp)
        if h == height[left]{
            left++
        }else{
            right--
        }
    }
    return ans
}

func max(x, y int) int{
    if x < y{
        return y
    }
    return x
}

func min(x, y int) int{
    if x < y{
        return x
    }
    return y
}

LeetCode 209

思路

就维护一个同向的双指针。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func minSubArrayLen(target int, nums []int) int {
    var low int
    var sum, ans int = 0, 100001
    for fast := 0; fast < len(nums); fast++{
        sum += nums[fast]
        // 舍弃前边的直到不符合条件（滑动窗口）
        for low < len(nums) && sum >= target{
            ans = min(ans, fast - low + 1)
            sum -= nums[low]
            low++
        }
    }
    // 如果是初始值表示没有满足条件的长度
    if ans == 100001{
        ans = 0
    }
    return ans
}

func min(x, y int) int{
    if x < y{
        return x
    }
    return y
}

LeetCode 713

思路

本题最重要的一行代码就是：

ans += fast - low + 1

这里引用官解评论区中的一个评论来说，当我们遍历到 fast 时，我们需要计算包含最右边数字的子串数量，因为左侧数字子串的数量我们已经统计过了。举例来说就是 [10, 5]，当我们遍历到 5 时，如果 5 是满足加入条件，只需要加入 [10, 5] 和 [5]。而这部分的数量正好是 r - l + 1。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
func numSubarrayProductLessThanK(nums []int, k int) int {
    var low int
    var mul, ans int = 1, 0
    for fast := 0; fast < len(nums); fast++{
        mul *= nums[fast]
        for low <= fast && mul >= k{
            mul /= nums[low]
            low++
        }
        ans += fast - low + 1
    }
    return ans
}

LeetCode 3

思路

本题的一个重要思路受 无重复字符的最长子串题解 的启发。

将滑动窗口形容成队列。比如在遍历 “abcabcbb” 的时候，”abc” 先加入到队列中，当碰到 “abca” 时，左侧的 a 需要出队。那么，碰到 “bcaa” 的时候，就需要将 “bca” 都出队，因为碰到了重复元素。这一子串是不符合条件的。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func lengthOfLongestSubstring(s string) int {
    var fast,ans int = -1, 0
    var repeatMap = make(map[byte]int)
    for low := range s{
        if low > 0{
            // 这里是 low 移动了，移除左边的元素
            delete(repeatMap, s[low - 1])
        }
        for ;fast + 1 < len(s) && repeatMap[s[fast + 1]] == 0;fast++{
            // 右指针开始移动，当碰到重复元素时，左指针移动
            repeatMap[s[fast + 1]]++
        }
        ans = max(ans, fast - low + 1)
    }
    return ans
}

func max(x, y int) int{
    if x > y{
        return x
    }
    return y
}

LeetCode 1004

思路

关键在于窗口维护一个 cnt，当 cnt > k 时达到了可替换的最大数，慢指针往前移动，遇到 0 时 cnt–。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func longestOnes(nums []int, k int) int {
    var low, ans, cnt int
    for fast := range nums{
      if nums[fast] == 0{
          cnt++
      }
      for cnt > k {
        if nums[low] == 0{
          cnt--
        }
        low++
      }
      ans = max(ans, fast - low + 1)
    }
    return ans
}

func max(x, y int) int{
  if x < y{
    return y
  }
  return x
}

LeetCode 1234

思路

最重要的是：

  1. 当 cnt 内的各个元素出现次数都小于等于 m（每个元素均分出现的次数）时，才可以替换掉外面的字符使其变成平衡字符串。
  2. 也就是，如果 cnt 内有元素出现次数大于 m，那么无论外面怎么替换都是不平衡的。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func balancedString(s string) int {
    m := len(s) / 4
    var cnt = make(map[byte]int)
    for i := range s{
        cnt[s[i]]++
    }

    if cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m{
        // 如果四个字母的出现次数都等于 m，直接返回
        return 0
    }

    var low,ans = 0, len(s)
    for fast := range s{
        cnt[s[fast]]--
        for cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m{
            // 如果四个字母的出现次数都小于等于 m
            ans = min(ans, fast - low + 1)
            cnt[s[low]]++
            low++
        }
    }
    return ans
}

func min(x, y int) int{
    if x < y{
        return x
    }
    return y
}

LeetCode 1658

思路

关键：转换成找一个满足和为 target 的最长子数组。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func minOperations(nums []int, x int) int {
    // 转换成找一个满足和 target 的最长子数组
    var target = -x
    for i := range nums{
        target += nums[i]
    }
    if target < 0{
        return -1
    }
    
    var ans,low,sum int = -1, 0, 0
    for fast := range nums{
        sum += nums[fast]
        for sum > target{
            sum -= nums[low]
            low++
        }
        if sum == target{
            ans = max(ans, fast - low + 1)
        }
    }

    if ans == -1{
        return ans
    }
    return len(nums) - ans
}

func max(x,y int) int{
    if x < y{
        return y
    }
    return x
}