双指针算法总结

双指针算法类型

  双指针的问题主要可以归为两类，一类是「快慢指针」，主要解决链表中的问题，比如典型的判定链表中是否包含环；另一类是「左右指针」，主要解决数组（或者字符串）中的问题，比如二分查找。

快慢指针的常见算法

  快慢指针一般都初始化指向链表的头结点 head，前进时快指针 fast 在前，慢指针 slow 在后，巧妙解决一些链表中的问题。

判断链表中是否有环

  单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的。如果链表中不含环，那么这个指针最终会遇到空指针 nil 表示链表到头了，这还好说，可以判断该链表不含环：

func hasCycle(head *ListNode) bool {
	for head != nil {
    head = head.Next
  } 
  return false
}

  但是如果链表中含有环，那么这个指针就会陷入死循环，因为环形数组中没有 nil 指针作为尾部节点。经典解法就是用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 nil，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。

环形链表

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
    fast := head
    slow := head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}

已知链表中含有环，返回这个环的起始位置

环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：你是否可以使用 O(1) 空间解决此题？

  当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。这是为什么呢？

第一次相遇时，假设慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步：

fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。

说句题外话，之前还有读者争论为什么是环长度整数倍，我举个简单的例子你就明白了，我们想一想极端情况，假设环长度就是 1，如下图：

那么 fast 肯定早早就进环里转圈圈了，而且肯定会转好多圈，这不就是环长度的整数倍嘛。

言归正传，设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。你甭管 fast 在环里到底转了几圈，反正走 k 步可以到相遇点，那走 k - m 步一定就是走到环起点了：

所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后就会相遇，相遇之处就是环的起点了。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    fast := head
    slow := head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            slow = head
            break
        }
    }
  // 上面的代码类似 hasCycle 函数

    if fast == nil || fast.Next == nil {
      // fast 遇到空指针说明没有环
        return nil
    }

    for {
        if fast == slow {
            return fast
        }
        fast = fast.Next
        slow = slow.Next
    }
}

链表的中间结点

  类似上面的思路，我们可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    fast := head
    slow := head

    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        
    } 
    return slow
}

当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右：

查找链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

  还是使用快慢指针，让快指针先走 n 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 nil 时，慢指针所在的位置就是倒数第 n 个链表节点（n 不会超过链表长度）。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    fast := head
    slow := head

    for i:=0;i<n;i++ { // 快指针先走n步
        fast = fast.Next
    }
    if fast == nil {
        head = head.Next
        return head
    }
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next  // 删除这个节点
    return head
}

回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

  这道题看似很简单，只需要将链表存到数组中，从数组两端开始向中间依次比较，只要有两端的数字不同，立即返回false。可是这样做的空间复杂度为O(n)，有什么办法能将空间复杂度控制为O(1)呢？

  这道题集成了快慢指针，反转链表的操作，很具有代表性。我们要避免使用O(n)的额外空间，就要改变输入，我们可以通过反转后半部分链表，然后将前半部分与后半部分进行比较。该方法可以将空间复杂度降到O(1)，但是在并发环境下，该方法也有缺点，在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

算法流程：

1.找到前半部分链表的尾节点：可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。若链表有奇数个节点，则中间的节点应该看作是前半部分。

2.反转后半部分链表：同反转链表的解决方案。

3.判断是否回文：比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

4.返回结果。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {

    if head == nil || head.Next == nil {
        return true
    }
  
    fast, slow := head, head
    for fast != nil && fast.Next != nil { // 快慢指针找到中间节点
        fast = fast.Next.Next
        slow = slow.Next
    }
    if fast == nil { // 该链表有偶数个节点
        s := reverse(slow)          
        for s != nil {
            if head.Val != s.Val {
                return false
            }
            s = s.Next
            head = head.Next
        }
    } else {  // 该链表有奇数个节点
        s := reverse(slow.Next)
        for s != nil {
            if head.Val != s.Val {
                return false
            }
            s = s.Next
            head = head.Next
        }
    }
    return true
}

func reverse(p *ListNode) *ListNode {  // 反转链表
    h := p
    q := p.Next
    for q != nil {
        temp := q.Next
        q.Next = p
        p = q
        q = temp
    }
    h.Next = nil
    return p
}

左右指针的常见算法

  左右指针在数组中实际是指两个索引值，一般初始化为left:=0, right:=len(array)-1。常见的左右指针算法通常分为四类：1.二分查找；2.两数之和；3.反转数组；4.滑动窗口。其中以滑动窗口最为困难，已经有专门的专题滑动窗口(Sliding Window)算法框架来介绍。其他三类只要掌握了基本框架，基本都能解决。

二分查找

二分查找的三种基本框架

1.寻找某一个特定的数(最基本的二分查找)

func binarySearch(nums []int, target int) int {
	left := 0
  	right := len(nums)-1
  
  	for left <= right {  // 注意符号
  			mid := left + (right-left)/2  // 如果使用(left+right)/2的方式，可能导致溢出
    		if nums[mid] == target {  // 一旦找到。立即返回
      			return mid
        } else if nums[mid] < target {
          	left = mid + 1  // 注意
        } else {
          	right = mid - 1  // 注意
        }
  	}
		return -1
}

值得注意的地方(也是区分于其他框架的地方)：

• 循环中符号是<=
• 一旦nums[mid]查找到，立即返回mid
• left = mid + 1 right = mid - 1

2.寻找左侧边界的二分查找

  这个左边界不仅限于target存在于数组中，也可以找到其不在数组时的左边界。举例如下：

nums[] = {2,3,4,5,5,5,6,9,17} , target=5, 其左边界为索引3

nums[] = {2,2,3,4,4,4,6,7,7,8,9,456}, target=5, 其左边界索引为5

func left_bound(nums []int, target int) int {
  	if len(nums) == 0 {
    		return -1 
  	}
  	left := 0
  	right := len(nums) - 1
  	
  	for left < right {  // 注意符号
      	mid := left + (right-left)/2
      	if nums[mid] == target {
        		right = mid // 注意
        } else if nums[mid] < target {
          	left = mid + 1 // 注意
        } else {
          	right = mid // 注意
        }
  	} 
  
  	if nums[left] == target { // 等于target，直接返回左边界
        return left
    } else if nums[len(nums)-1] < target { // 如果最后一个数都小于target，此时left指向的是最后一个数，此时将其最为左边界的话直接返回left。如果在一开始就对边界情况做了判断，就不需要对这一条件做判断
        return left  // left=len(nums)-1
    } else {
		return left-1
    }
}

值得注意的地方:

• 循环中符号是<，所以当数组只有一个元素时，不会进入for循环，要单独判断；因为是小于符号，所以出循环，left和right都不可能越界，这就意味着如果数组最后一个数 < target，按理说要返回前一个数的索引，但是由于right卡在了数组末尾元素上，循环结束的条件是left=right，所以此时左边界直接返回left，而不需要left-1
• 查找到nums[mid]=target，不直接返回，让right=mid，锁定住
• left = mid+1 right = mid
• 最终判断一下nums[left]是否等于target，等于说明target在数组中，直接返回left，否则返回left-1
• 找左边界的时候记得优先判断一下有序数组中最后一个数是否大于target，若最大的数都小于target，说明整个数组的左边界只能由最后一位数来担任，left=len(nums)-1

3.寻找右侧边界的二分查找

  这个右边界不仅限于target存在于数组中，也可以找到其不在数组时的右边界。举例如下：

nums[] = {2,3,4,5,5,5,6,9,17} , target=5, 其右边界为索引5

nums[] = {2,2,3,4,4,4,6,7,7,8,9,456}, target=5, 其右边界索引为6

func right_bound(nums []int, target int) int {
  	if len(nums) == 0 {
    	return -1 
  	}
  	left := 0
  	right := len(nums) - 1
  	
  	for left < right {  // 注意符号
      	mid := left + (right-left)/2
      	if nums[mid] == target {
        		left = mid + 1 // 注意
        } else if nums[mid] < target {
          	left = mid + 1 // 注意
        } else {
          	right = mid // 注意
        }
  	} 
  	
  	if nums[left] == target { // 第一位数或最后一位数作为右边界，如果在一开始就对边界情况做了判断，可以不需要对这一个条件做判断
    	return 0
  	} else if nums[left-1] == target {  // 注意
    	return left-1
  	} else {
    	return left
  	}
}

值得注意的地方:

• 循环中符号是<，所以当数组只有一个元素时，不会进入for循环，要单独判断；因为是小于符号，所以出循环，left和right都不可能越界，这就意味着如果数组第一个数 > target，left一定会一直卡在索引0位置上，循环结束的条件是left=right，所以此时left=0，要判断nums[left-1]是否等于target，显然发生了越界，所以直接使用left(=0)作为右边界
• 查找到nums[mid]=target，不直接返回，让left = mid + 1，锁定住
• left = mid + 1 right = mid
• 最终判断一下nums[left-1]是否等于target，等于说明target在数组中，直接返回left-1，否则返回left

  寻找左右边界这两个框架出来的left其实可以看成是一个永远指向target右侧的一个指针(不管这个target是否在数组中)，见下面示意：

··· ···, a, a, a, [b, b, b, b,] c, c, c, ··· ···

• b是target，[]表示其可能存在在数组中，当找其左边界时，left指针所在位置如下：

  ··· ···, a, a, a, [b(left), b, b, b,] c, c, c, ··· ···

  当b存在在数组中，则直接输出left，当b不在数组中，则a是其左边界，输出left-1

• b是target，[]表示其可能存在在数组中，当找其右边界时，left指针所在位置如下：

  ··· ···, a, a, a, [b, b, b, b,] c(left), c, c, ··· ···

  当b存在在数组中，则输出left-1，当b不在数组中，则c是其有边界，输出left

总而言之，首先考虑数组只有一个元素或没有元素的情况。之后将target和首位元素做比较，看首位元素是否是其左右边界，或者target可能干脆就不在这个数组的范围内。之后再正式套用上述框架来找左右边界。

寻找旋转排序数组中的最小值 II

  已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

示例 1：

输入：nums = [1,3,5]
输出：1

示例 2：

输入：nums = [2,2,2,0,1]
输出：0

提示：

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

  该题相当于要找到数组中最小值的左边界(最小值可能不止一个)。left指针移动的条件是当mid指针所指的数大于right指针所指数，那么mid所指的数一定不可能是边界区域，left=mid+1。当出现nums[mid]<nums[right]时，说明nums[mid]已经在最小值左边界的右方，此时固定住right指针，继续二分查找。有区别的是当出现nums[mid]=nums[right]的情况时，原先的二分查找是严格的赠序数组，可以直接让right=mid，锁定住右边界。但是如出现下面的情况：nums数组为**[3,3,1,3]**，直接让right=mid会跳过中间的小值，所以只需要让right指针减一，缩小搜索范围即可。

func findMin(nums []int) int {
    left := 0
    right := len(nums)-1

    for left<right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid+1
        } else if nums[mid] < nums[right] {
            right = mid
        } else {
            right--
        }
    }
    return nums[left]
}

搜索旋转排序数组 II

  已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

  在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

  给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

解题思路：

   找目标数，首先考虑二分查找。但是本题的数组在[left,mid]和[mid,right]两段区间内只有一段是有序的。要用二分查找找target，就必须在有序的区间查找。所以要理清可能出现的三种情况：

• 第一类

  对于数组中有重复元素的情况，二分查找时可能会有 nums[lelf]=nums[mid]=nums[right]，此时无法判断区间 [left,mid] 和区间[mid+1,right]哪个是有序的。例如 nums=[3,1,2,3,3,3,3]，target=2，首次二分时无法判断区间 [0,3] 和区间 [4,6] 哪个是有序的。对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

• 第二类

  nums=[2,3,4,5,6,7,1] 这种，也就是 nums[left] < nums[mid]。此例子中就是 2 < 5；这种情况下，前半部分有序。因此如果 nums[left]<=target<nums[mid]，则在前半部分找，否则去后半部分找。

• 第三类

  nums=[6,7,1,2,3,4,5]这种，也就是 nums[left] > nums[mid]。此例子中就是 6 > 2；这种情况下，后半部分有序。因此如果 nums[mid]<target<=nums[right]。则在后半部分找，否则去前半部分找。

func search(nums []int, target int) bool {
    left := 0
    right := len(nums)-1

    for left <= right {  // 找具体的数，用<=
        mid := left + (right-left)/2

        if nums[mid] == target {
            return true
        }

        if nums[left] == nums[mid] && nums[mid] == nums[right] {  //第一类情况
            left++
            right--
        } else if nums[left] <= nums[mid] {  // 左边有序
            if nums[left] <= target && nums[mid] > target {
                right = mid-1  // 在前半部分找
            } else {
                left = mid+1   // 在后半部分找
            }
        } else { // 右边有序 
            if nums[mid] < target && nums[right] >= target {
                left = mid+1   // 在后半部分找
            } else {
                right = mid-1  // 在前半部分找
            }
        }
    }
    return false
}

在 D 天内送达包裹的能力

  传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

  传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

  返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 

示例 2：

输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4

示例 3：

输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1

提示：

1 <= D <= weights.length <= 5 * 104
1 <= weights[i] <= 500

算法思路：

  假设当船的运载能力为 x 时，我们可以在 days 天内运送完所有包裹，那么只要运载能力大于 x，我们同样可以在 days 天内运送完所有包裹：我们只需要使用运载能力为 x 时的运送方法即可。

  这样一来，我们就得到了一个非常重要的结论：

存在一个运载能力的「下限」$$x _\text { ans }$$，使得当 x ≥ $$x _\text { ans }$$时，我们可以在 days 天内运送完所有包裹；当 x<
$$x _\text { ans }$$时，我们无法在 days 天内运送完所有包裹。

  同时，$$x _\text { ans }$$即为我们需要求出的答案。因此，我们就可以使用二分查找的方法找出 $$x _\text { ans }$$的值。在二分查找的每一步中，我们实际上需要解决一个判定问题：给定船的运载能力 x，我们是否可以在 days 天内运送完所有包裹呢？这个判定问题可以通过贪心的方法来解决：

  由于我们必须按照数组 weights 中包裹的顺序进行运送，因此我们从数组 weights 的首元素开始遍历，将连续的包裹都安排在同一天进行运送。当这批包裹的重量大于运载能力 x 时，我们就需要将最后一个包裹拿出来，安排在新的一天，并继续往下遍历。当我们遍历完整个数组后，就得到了最少需要运送的天数。

  我们将「最少需要运送的天数」与 days 进行比较，就可以解决这个判定问题。当其小于等于 days 时，我们就忽略二分的右半部分区间；当其大于 days 时，我们就忽略二分的左半部分区间。

细节

二分查找的初始左右边界应当如何计算呢？

对于左边界而言，由于我们不能「拆分」一个包裹，因此船的运载能力不能小于所有包裹中最重的那个的重量，即左边界为数组 weights 中元素的最大值。

对于右边界而言，船的运载能力也不会大于所有包裹的重量之和，即右边界为数组 weights 中元素的和。

我们从上述左右边界开始进行二分查找，就可以保证找到最终的答案。

func shipWithinDays(weights []int, days int) int {
    left := weights[0]
    right := 0
    for i:=0; i<len(weights); i++ {
        if weights[i] > left {  // 设置运载能力左边界为货物中最大重量
            left = weights[i]
        }
        right += weights[i]			// 设置运载能力有边界为货物总重量
    }

    var check func(cap int) bool
    check = func(cap int) bool {
        temp := 0 // 一天内运送货物重量的累积
        day := 0

        for _, v := range weights {
            if cap < temp+v {  // 超过🚢的运载能力，天数+1
                day++
                temp = 0
            }
            temp += v
        }
        if temp != 0 {
            day++
        }
        if day<=days {
            return true
        } else {
            return false
        }
    }

    for left < right { // 二分查找满足运送天数的🚢运载能力的左边界
        mid := left + (right-left)/2

        if check(mid) {
            right = mid
        } else {
            left = mid+1
        }
    }
    return left
}

搜索二维矩阵

  编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

  对于本题，主要的思路就是先通过对每行的首个数字组成的序列进行二分查找，首先要判断target是否在最后一行中，如果是的话，直接在最后一行进行二分查找。这么做的目的是如果直接二分查找target的左边界，如果最后一行的首位数小于target，此时不能将接下来继续二分查找的行数定位left-1，要直接在left行(也就是最后一行)进行查找。简单来说，left的最大值只可能是len(matrix)-1，然而要找的左边界是left-1，这样最后一行永远都无法被选中。读者可以自己找一个实际的例子来看一看。

  若不在最后一行，那么就进行二分查找找到target的左边界，这时会出现两种情况：

• 左边界恰好是要找的target，直接返回true
• 左边界位于非最后一行，定位到target可能出现的那一行row=left-1

  最后再在找到的行进行二分查找。

func searchMatrix(matrix [][]int, target int) bool {
    left := 0
    right := len(matrix)-1

    r := len(matrix) // 行数
    c := len(matrix[0])  // 列数
    var row int
		
  	// 边界情况：target超出了二维数组的范围，直接返回false
    if target < matrix[0][0] || target > matrix[r-1][c-1] {
        return false
    }

    if r > 1 && matrix[r-1][0] > target { // 当不止有一行并且target不在最后一行时
        for left < right { // 找左边界，可以参考模板2
            mid := left + (right-left)/2
            if matrix[mid][0] == target {
                right = mid
            } else if matrix[mid][0] < target {
                left = mid+1
            } else {
                right = mid
            }
        }
        if matrix[left][0] == target { // 如果left指向的数等于target，直接返回true
            return true
        } else {  // 否则可以定位target可能出现的行号
            row = left-1
        }
    } else if r == 1 {  // 如果只有一行，则无需二分查找
        row = 0
    } else {  // 如果target可能出现在最后一行
        row = r-1
    }

    leftRow := 0
    rightRow := c-1

    for leftRow <= rightRow { // 使用二分查找在确定的行上查找
        mid := leftRow + (rightRow-leftRow)/2

        if matrix[row][mid] == target {
            return true
        } else if matrix[row][mid] > target {
            rightRow = mid-1
        } else {
            leftRow = mid+1
        }
    }
    return false
}

搜索二维矩阵 II

  编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

算法思路：

  不同于上一题每一行的第一个元素大于前一行的第一个元素，本题要暴力搜索的话需要对每一行进行二分查找。可以考虑先确定目标数可能存在于哪几行内，对这几行进行搜索即可。

• 对每行的最后一个元素进行二分查找，寻找target的左边界，可以确定起始行号
• 对每一行第一个元素进行二分查找，寻找target的左边界，可以确定终止行号

func searchMatrix(matrix [][]int, target int) bool {
    r, c := len(matrix)-1,len(matrix[0])-1

    row1 := 0
    row2 := 0

    if matrix[r][c] < target { // 如果最后一个元素小于target，直接返回false
        return false
    } else if matrix[r][c] == target {
        return true
    } else {
        left,right := 0,r
        for left<right {
            mid := left + (right-left)/2
            if matrix[mid][c] == target {
                return true
            } else if matrix[mid][c] > target {
                right = mid
            } else {
                left = mid+1
            }
        }
        row2 = left // 起始行号=左边界+1
    }

    if matrix[r][0] < target {
        row1 = r
    } else if matrix[r][0] == target {
        return true
    } else {
        left,right := 0,r
        for left<right {
            mid := left + (right-left)/2
            if matrix[mid][0] == target {
                return true
            } else if matrix[mid][0] > target {
                right = mid
            } else {
                left = mid+1
            }
        }
        row1 = left-1 // 终止行号=左边界
    }
    // fmt.Println(row2)
    // fmt.Println(row1)

    if row2>row1 {
        return false
    }
    for row2 <= row1 {  // 对可能的行内进行二分查找
        left,right := 0,c
        for left<=right {
            mid := left + (right-left)/2
            if matrix[row2][mid] == target {
                return true
            } else if matrix[row2][mid] < target {
                left = mid+1
            } else {
                 right = mid-1
            }
        }
        row2++
    }
    return false
}

在排序数组中查找元素的第一个和最后一个位置

  给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

解题思路：

  本题直接找左右边界即可，首先判断边界情况：

• 数组为空，直接返回[-1,-1]
• 数组只有一个元素，若该元素=target，返回[0,0]；否则，返回[-1,-1]

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

    if len(nums) == 1 && nums[0] == target {
        return []int{0,0}
    } else if (len(nums) == 1 && nums[0] != target) || len(nums) == 0 {
        return []int{-1,-1}
    }

    left := 0
    right := len(nums)-1
    ret := []int{}

    for left < right { // 找左边界
        mid := left + (right-left)/2

        if nums[mid] == target {
            right = mid
        } else if nums[mid] < target {
            left = mid+1
        } else {
            right = mid
        }
    }

    if nums[left] == target {
        ret = append(ret, left)
    } else {  // 找不到target，其左边界是数组中最大的比它小的数
        return []int{-1,-1}
    }

    left = 0
    right = len(nums)-1

    for left < right {    // 找右边界
        mid := left + (right-left)/2

        if nums[mid] == target {
            left = mid+1
        } else if nums[mid] < target {
            left = mid+1
        } else {
            right = mid
        }
    }
  
  	// 因为在找左边界的时候已经判断过该数组中是否存在target，能到这一步肯定是存在的。不用顾虑第一个数大 于target的情况
    if nums[left] == target { // 右边界是数组第一个数
        ret = append(ret,left)
    } else { // 右边界是其他数
        ret = append(ret, left-1)
    }
    
    return ret
}

两数之和类题目

两数之和

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

  你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

  你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

func twoSum(nums []int, target int) []int {
	  sort.Ints(nums)  // 给数组排序
  	l, r := 0, len(nums)-1
  	ret := []int{}
  
  	if len(nums)<2 {
    		return ret
  	}
  
  	for l < r {
     		if nums[l]>target {
        		break
      	}
      	if nums[l]+nums[r] == target {
        		ret = append(ret,l,r)
        } else if nums[l]+nums[r] > target {
          	r--
        } else {
          	l++
        }
  	}
  	return ret
}

本题也可使用map来做

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for index, value := range nums {
        another := target - value
        _, ok := m[another]
        if ok {
            return []int{index, m[another]}
        }
        m[value] = index      
    }
    return []int{}
}

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

算法思路：

  整体思路和两数之和非常像，不过是通过遍历数组固定第一个数，后两个数使用双指针的方式进行查找。注意的是不能输出重复的三元组，所以在遍历的要判断一下是否和之前的数相等，相等则跳过该数。

func threeSum(nums []int) [][]int {
    if len(nums)<3 {
        return [][]int{}
    }

    if len(nums) == 3 {
        if nums[0]+nums[1]+nums[2]==0 {
            return [][]int{nums}
        } else {
            return [][]int{}
        }
    }

    sort.Ints(nums)  // 排序数组
    res := [][]int{}

    for k:=0; k<len(nums)-2; k++ {
        if nums[k] > 0 { // 如果最小的数都大于0，直接结束循环
            break
        }
        if k>0 && nums[k] == nums[k-1] { // 为避免重复，跳过已经出现的数
            continue
        }
        
        tmp := nums[k]
        i,j := k+1,len(nums)-1
        for i<j {
            if tmp+nums[i]+nums[j] == 0 {
                res = append(res,[]int{tmp,nums[i],nums[j]})
                i++
                j--
                for i<j && nums[i] == nums[i-1] { // 为避免重复，跳过已经出现的数
                    i++
                }
                for i<j && nums[j] == nums[j+1] { // 为避免重复，跳过已经出现的数
                    j--
                }
            } else if tmp+nums[i]+nums[j] > 0 {
                j--
            } else {
                i++
            }           
        }
    }
    return res
}

四数之和

  给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [], target = 0
输出：[]

提示：

0 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

  类似于三数之和，不过是在三数之和最外层再套一个for循环。

func fourSum(nums []int, target int) [][]int {
    if len(nums) < 4 {
        return [][]int{}
    }
    if len(nums) == 4 {
        if nums[0]+nums[1]+nums[2]+nums[3] == target{
            return [][]int{[]int{nums[0],nums[1],nums[2],nums[3]}}
        }
    }

    res := [][]int{}
    sort.Ints(nums)  // 首先进行排序

    for i:=0; i<len(nums)-3; i++ { // 最外层循环，固定四元组的第一位

        if i>0 && nums[i]==nums[i-1] { // 过滤掉可能出现相同四元组的情况
            continue
        }

        for j:=i+1; j<len(nums)-2; j++ { // 中层循环，遍历数组选择住四元组的第二位
            if j>i+1 && nums[j]==nums[j-1] { // 过滤掉可能出现相同四元组的情况
                continue
            }

            l,r := j+1,len(nums)-1
            for l<r { // 内层循环，双指针选择四元组的最后两位
                if nums[i]+nums[j]+nums[l]+nums[r] == target {
                    res = append(res,[]int{nums[i],nums[j],nums[l],nums[r]})
                    l++
                    r--
                    for l<r && nums[l]==nums[l-1] { // 过滤掉可能出现相同四元组的情况
                        l++
                    }
                    for l<r && nums[r]==nums[r+1] { //过滤掉可能出现相同四元组的情况
                        r--
                    }
                } else if nums[i]+nums[j]+nums[l]+nums[r] < target {
                    l++
                } else {
                    r--
                }
            }
        }
    }
    return res
}

反转数组

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

func reverseString(s []byte)  {
    l,r := 0,len(s)-1
    for l<r {
        s[l],s[r] = s[r],s[l]
        l++
        r--
    }
}

补充：剑指 Offer 24. 反转链表

  定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解题思路：

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {

    if head == nil || head.Next == nil {
        return head
    }
    if head.Next.Next == nil {
        p := head.Next
        p.Next = head
        head.Next = nil
        return p
    }
    first,second,third := head,head.Next,head.Next.Next
    first.Next = nil
    for third.Next != nil {
        second.Next = first
        first = second
        second = third
        third = third.Next
    }
    third.Next = second
    second.Next = first
    return third
}

滑动窗口算法

  这个类型的题目是很有难度的，有专门的文章进行介绍。滑动窗口(Sliding Window)算法框架

参考资料

双指针技巧总结