双指针

Problems

LeetCode 0005 最长回文子串 (中等, 2021-10)
LeetCode 0011 盛最多水的容器 (中等, 2021-10)
LeetCode 0015 三数之和 (中等, 2021-10)
LeetCode 0016 最接近的三数之和 (中等, 2021-10)
LeetCode 0042 接雨水 (困难, 2021-10)
LeetCode 0167 两数之和2(输入有序数组) (简单, 2021-10)
LeetCode 0611 有效三角形的个数 (中等, 2021-10)
剑指Offer 2100 调整数组顺序使奇数位于偶数前面 (简单, 2021-11)
剑指Offer 4800 最长不含重复字符的子字符串 (中等, 2021-12)
剑指Offer 5701 和为s的两个数字 (简单, 2022-01)
剑指Offer 5702 和为s的连续正数序列 (简单, 2022-01)
剑指Offer 5801 翻转单词顺序 (简单, 2022-01)
牛客 0022 合并两个有序的数组 (中等, 2022-01)

`LeetCode 0005 最长回文子串 (中等, 2021-10)`

问题简述

给你一个字符串 s，找到 s 中最长的回文子串。

5. 最长回文子串 - 力扣（LeetCode）

详细描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
    输入：s = "babad"
    输出："bab"
    解释："aba" 同样是符合题意的答案。
示例 2：
    输入：s = "cbbd"
    输出："bb"
示例 3：
    输入：s = "a"
    输出："a"
示例 4：
    输入：s = "ac"
    输出："a"

提示：
    1 <= s.length <= 1000
    s 仅由数字和英文字母（大写和/或小写）组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：动态规划

状态定义：dp[i][j] := 子串 s[i:j] 是否为回文串；
状态转移方程：dp[i][j] := dp[i+1][j-1] == True 且 s[i] == s[j]；
初始状态
- 单个字符：dp[i][j] := True 当 i == j
- 两个连续相同字符：dp[i][j] := True 当 j == i + 1 && s[i] == s[j]

注意：

动态规划并不是最适合的解，这里仅提供一个思路；
如果要使用动态规划解本题，如何循环是关键，因为回文串的特点，从“双指针”的角度来看，需要从中心往两侧遍历，这跟大多数的 dp 问题略有不同；

C++

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();

        vector<vector<int>> dp(n, vector<int>(n, 0));
        int max_len = 1;    // 保存最长回文子串长度
        int start = 0;      // 保存最长回文子串起点

        // 初始状态1：子串长度为 1 时，显然是回文子串
        for (int i = 0; i < n; i++)
            dp[i][i] = 1;

        //for (int j = 1; j < n; j++)         // 子串结束位置
        //    for (int i = 0; i < j; i++) {   // 子串起始位置
        // 上述循环方式也是可以的，但在 “最长回文子序列” 一题中会有问题
        // 下面的循环方式在两个问题中都正确，这个遍历思路比较像“中心扩散法”
        for (int j = 1; j < n; j++)             // 子串结束位置
            for (int i = j - 1; i >= 0; i--) {  // 子串开始位置
                if (j == i + 1)  // 初始状态2：子串长度为 2 时，只有当两个字母相同时才是回文子串
                    dp[i][j] = (s[i] == s[j]);
                else  // 状态转移方程：当上一个状态是回文串，且此时两个位置的字母也相同时，当前状态才是回文串
                    dp[i][j] = (dp[i + 1][j - 1] && s[i] == s[j]);

                // 保存最长回文子串
                if (dp[i][j] && max_len < (j - i + 1)) {
                    max_len = j - i + 1;
                    start = i;
                }
            }

        return s.substr(start, max_len);
    }
};

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            dp[i][i] = 1
        
        start = 0
        length = 1
        for j in range(1, n):  # 子串的结束位置
            for i in range(j - 1, -1, -1):  # 子串的开始位置
                if i == j - 1:
                    dp[i][j] = 1 if s[i] == s[j] else 0
                else:
                    dp[i][j] = 1 if dp[i + 1][j - 1] and s[i] == s[j] else 0

                if dp[i][j]:
                    if j - i + 1 > length:
                        length = j - i + 1
                        start = i

        return s[start: start + length]

思路2：模拟-中心扩散（推荐）

按照回文串的定义，遍历每个字符作为中点，向两边扩散；
官方题解从 DP 的转移方程解释了为什么中心扩散可以得到正确答案（虽然这个结论非常直观），观察状态转移方程，可以看到所有状态在转移时的可能性都是唯一的：dp[i][j] <- dp[i+1][j-1] <- dp[i+2][j-2] <- ...，也就是说，从每一种边界情况开始「扩展」，都可以得出所有状态对应的答案。

最长回文子串 - 力扣官方题解

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:

        n = len(s)
        self.ret = s[0]

        # 从 s[l:r] 开始向两侧扩散，开始时，l==r 或者，l+1==r
        def process(l, r):
            tmp = ''
            while l >= 0 and r < n:
                if s[l] != s[r]:
                    break
                tmp = s[l: r + 1]
                l -= 1
                r += 1

            if len(tmp) > len(self.ret):
                self.ret = tmp

        for l in range(n - 1):
            process(l, l)
            process(l, l + 1)

        return self.ret

`LeetCode 0011 盛最多水的容器 (中等, 2021-10)`

问题描述

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：不能倾斜容器。

示例 1：
    输入：[1,8,6,2,5,4,8,3,7]
    输出：49 
    解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

首尾双指针遍历

Python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """"""
        l, r = 0, len(height) - 1
        ret = (r - l) * min(height[l], height[r])  # 初始化

        while l < r:
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
            
            tmp = (r - l) * min(height[l], height[r])
            ret = max(ret, tmp)
            
        return ret

`LeetCode 0015 三数之和 (中等, 2021-10)`

问题简述

给定一个数组，找出该数组中所有和为 0 的三元组。

详细描述

给你一个包含 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
    -10^5 <= nums[i] <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

排序后，问题可以简化成两数之和（LeetCode-167）；
先固定一个数，然后利用首尾双指针进行对向遍历；
注意跳过相同结果；

Python

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # assert
        ret = []
        L = len(nums)
        if L < 3:
            return ret

        # 设置目标值
        target = 0
        # 排序
        nums = sorted(nums)

        for i in range(L - 2):  # 固定第一个数
            # 剪枝
            if i > 0 and nums[i] == nums[i - 1]: continue
            if nums[i] + nums[i + 1] + nums[i + 2] > target: break
            if nums[i] + nums[L - 2] + nums[L - 1] < target: continue

            # 设置左右指针
            l, r = i + 1, L - 1
            while l < r:

                s = nums[i] + nums[l] + nums[r]
                if s < target:
                    l += 1
                elif s > target:
                    r -= 1
                else:  # s == target
                    ret.append([nums[i], nums[l], nums[r]])

                    # 同时移动双指针
                    l += 1
                    r -= 1

                    # 如果跟上一个值相同，就跳过
                    while l < r and nums[l] == nums[l - 1]: l += 1
                    while l < r and nums[r] == nums[r + 1]: r -= 1

        return ret

`LeetCode 0016 最接近的三数之和 (中等, 2021-10)`

问题简述

给定一个数组，找出该数组中和最接近指定值的三元组。

详细描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：
    输入：nums = [-1,2,1,-4], target = 1
    输出：2
    解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：
    3 <= nums.length <= 10^3
    -10^3 <= nums[i] <= 10^3
    -10^4 <= target <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路跟三数之和基本一致；
当找到比当前更接近的结果时更新；

Python

from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        """"""
        nums = sorted(nums)

        L = len(nums)
        ret = nums[0] + nums[1] + nums[2]  # 初始化，len(nums) >= 3
        for i in range(L - 2):

            # 跳过重复元素
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # 利用单调性剪纸
            min_s = nums[i] + nums[i + 1] + nums[i + 2]  # 最小和
            if min_s > target:
                if abs(min_s - target) < abs(ret - target):
                    ret = min_s
                break

            max_s = nums[i] + nums[L - 2] + nums[L - 1]  # 最大和
            if max_s < target:
                ret = max_s
                continue

            # 初始化双指针
            l, r = i + 1, L - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if abs(s - target) < abs(ret - target):
                    ret = s

                if s < target:
                    l += 1
                    while l < r and nums[l] == nums[l - 1]: l += 1
                elif s > target:
                    r -= 1
                    while l < r and nums[r] == nums[r + 1]: r -= 1
                else:  # ret == target
                    return ret
        return ret

利用单调性剪枝

在经过排序后，每轮迭代时，三数之和的最大值和最小值是确定的；
所以如果最小值比目标值大，那么后面无论怎么移动双指针，差值都只会越来越大；最大值比目标值小时同理；

代码细节：

# 剪枝：利用单调性
min_s = nums[i] + nums[i + 1] + nums[i + 2]  # 最小和
if min_s > target:  # 如果最小和也大于 target，则剩余部分的差值肯定越来越大
    # 容易忽略的一步，注意此时也是有可能出现答案的，比如 ret < 0 < min_s 时
    if abs(min_s - target) < abs(ret - target):
        ret = min_s
    break

max_s = nums[i] + nums[L - 2] + nums[L - 1]  # 最大和
if max_s < target:  # 如果最大和也小于 target，则剩余部分的差值肯定越来越大
    ret = max_s  # 此时 ret < max_s < target，所以 max_s 必然比当前 ret 更接近目标值
    continue

`LeetCode 0042 接雨水 (困难, 2021-10)`

问题描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1（如图）：
    输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
    输出：6
    解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

法1）Python：双指针

class Solution:
    def trap(self, height: List[int]) -> int:
        """"""
        l, r = 0, len(height) - 1
        
        ans = 0
        max_l = max_r = 0  # 保存当前位置时，左右最高的柱子
        
        while l <= r:
            if height[l] <= height[r]:
                if height[l] > max_l:
                    max_l = height[l]
                else:
                    ans += max_l - height[l]
                l += 1
            else:
                if height[r] > max_r:
                    max_r = height[r]
                else:
                    ans += max_r - height[r]
                r -= 1
                
        return ans

法2）C++：左右遍历两次

class Solution {
public:
    int trap(vector<int>& H) {
        int n = H.size();
        
        vector<int> l_max(H);
        vector<int> r_max(H);
        
        for(int i=1; i<n; i++)
            l_max[i] = max(l_max[i-1], l_max[i]);
        
        for(int i=n-2; i>=0; i--)
            r_max[i] = max(r_max[i+1], r_max[i]);
        
        int ret = 0;
        for (int i=1; i<n-1; i++)
            ret += min(l_max[i], r_max[i]) - H[i];
        
        return ret;
    }
};

`LeetCode 0167 两数之和2(输入有序数组) (简单, 2021-10)`

问题简述

找出一个非递减数组中和等于 target 的两个数字，输出它们的下标。

假定题目一定有一个解。

详细描述

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

 
示例 1：
    输入：numbers = [2,7,11,15], target = 9
    输出：[1,2]
    解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
    输入：numbers = [2,3,4], target = 6
    输出：[1,3]
示例 3：
    输入：numbers = [-1,0], target = -1
    输出：[1,2]


提示：
    2 <= numbers.length <= 3 * 10^4
    -1000 <= numbers[i] <= 1000
    numbers 按 非递减顺序 排列
    -1000 <= target <= 1000
    仅存在一个有效答案

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

Python：双指针

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        """"""
        lo, hi = 0, len(numbers) - 1

        while lo < hi:
            tmp = numbers[lo] + numbers[hi]

            if tmp < target:
                lo += 1
            elif tmp > target:
                hi -= 1
            else:
                return [lo + 1, hi + 1]

`LeetCode 0611 有效三角形的个数 (中等, 2021-10)`

问题简述

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

详细描述

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:
    输入: [2,2,3,4]
    输出: 3
    解释:
    有效的组合是: 
    2,3,4 (使用第一个 2)
    2,3,4 (使用第二个 2)
    2,2,3
注意:
    数组长度不超过1000。
    数组里整数的范围为 [0, 1000]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-triangle-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

排序 + 首尾双指针；
相当于计算两数之和大于目标值的个数；

Python

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        """"""
        nums = sorted(nums)
        
        cnt = 0
        for i in range(2, len(nums)):  # 注意：循环区间
            
            lo, hi = 0, i - 1
            while lo < hi:
                s = A[lo] + A[hi]
                
                if s > A[i]:
                    cnt += hi - lo  # 范围剪枝
                    hi -= 1
                else:
                    lo += 1
                    
        return cnt

`剑指Offer 2100 调整数组顺序使奇数位于偶数前面 (简单, 2021-11)`

问题简述

给定整型数组，调整其顺序，使所有奇数在偶数之前（不要求顺序）。

详细描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例：
    输入：nums = [1,2,3,4]
    输出：[1,3,2,4] 
    注：[3,1,2,4] 也是正确的答案之一。
提示：
    0 <= nums.length <= 50000
    0 <= nums[i] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

头尾双指针，当头指针指向偶数，尾指针指向奇数时，交换；
注意边界判断；

Python

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:

        l, r = 0, len(nums) - 1
        while l < r:
            # 注意需要始终保持 l < r
            while l < r and nums[l] % 2 == 1:
                l += 1
            while l < r and nums[r] % 2 == 0:
                r -= 1
            
            nums[l], nums[r] = nums[r], nums[l]
        
        return nums

`剑指Offer 4800 最长不含重复字符的子字符串 (中等, 2021-12)`

问题简述

求字符串 s 中的最长不重复子串，返回其长度；

详细描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:
    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
        请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 
提示：
    s.length <= 40000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：双指针（推荐）

双指针同向遍历每个字符；同时使用哈希表记录每个字符的最新位置；
如果右指针遇到已经出现过的字符，则将左指针移动到该字符的位置，更新最大长度；
具体细节见代码；

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        
        c2p = dict()
        lo = -1  # 左指针
        ret = 1
        for hi, c in enumerate(s):  # 遍历右指针
            if c not in c2p or c2p[c] < lo:  # 如果当前字符还没有出现过，或者出现过但是在左指针的左侧，可以更新最大长度
                ret = max(ret, hi - lo)
            else:  # 否则更新左指针
                lo = c2p[c]

            c2p[c] = hi  # 更新字符最新位置

        return ret

思路2：动态规划

[最长不含重复字符的子字符串（动态规划 / 双指针 + 哈希表，清晰图解）](https://

状态定义 leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/)

记 dp[i] := 以第 i 个字符为结尾的不含重复字符的子串的最大长度；

转移方程

dp[i] = dp[i-1] + 1     if dp[i-1] < i-i
      = i-j             else

其中 j 表示字符 s[i] 上一次出现的位置；

使用一个 hash 表记录每个字符上一次出现的位置；
因为当前状态只与上一个状态有关，因此可以使用一个变量代替数组（滚动）；

初始状态

dp[0] = 1

Python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        idx = dict()
        ret = dp = 0
        for i, c in enumerate(s):
            if c not in idx:
                dp = dp + 1
            else:
                j = idx[c]  # 如果 c 已经出现过，获取其上一个出现的位置
                if dp < i - j:  # 参考双指针思路，这里相当于上一次出现的位置在左指针之前，不影响更新长度
                    dp = dp + 1
                else:  # 反之，在左指针之后
                    dp = i - j

            idx[c] = i  # 更新位置 i
            ret = max(ret, dp)  # 更新最大长度
        return ret

`剑指Offer 5701 和为s的两个数字 (简单, 2022-01)`

问题简述

给定一个递增数组和目标值 s，求数组中和为 s 的两个数；

详细描述

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。
如果有多对数字的和等于s，则输出任意一对即可。

示例 1：
    输入：nums = [2,7,11,15], target = 9
    输出：[2,7] 或者 [7,2]
示例 2：
    输入：nums = [10,26,30,31,47,60], target = 40
    输出：[10,30] 或者 [30,10]

限制：
    1 <= nums.length <= 10^5
    1 <= nums[i] <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

首尾双指针，相向遍历；

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        l, r = 0, len(nums) - 1

        while l <= r:
            s = nums[l] + nums[r]
            if s == target:
                return [nums[l], nums[r]]
            if s < target:
                l += 1
            else:
                r -= 1
        
        return []

`剑指Offer 5702 和为s的连续正数序列 (简单, 2022-01)`

问题简述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

详细描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：
    输入：target = 9
    输出：[[2,3,4],[4,5]]
示例 2：
    输入：target = 15
    输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：
    1 <= target <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：双指针

1 初始化 左边界 l = 1 ，右边界 r = 2，结果列表 ret = []；
2 循环 当 l + r <= target 时：
    记 l 到 r 的连续和为 s
    当 s > target 时： 向右移动左边界 l += 1；
    当 s < target 时： 向右移动右边界 r += 1；
    当 s = target 时： 记录连续整数序列，左右边界同时右移，l += 1, r += 1；
3 返回结果列表 ret；

Tips: 求连续和可以在移动双指针的过程中同步加减，并不需要每次用求和公式计算；

Python

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:

        l, r = 1, 2
        s = l + r

        ret = []
        while l + r <= target:
            if s > target:
                s -= l  # 先减
                l += 1
            elif s < target:
                r += 1
                s += r  # 后加
            else:
                ret.append(list(range(l, r + 1)))
                s -= l  # 先减
                l += 1
                r += 1
                s += r  # 后加

        return ret

思路2：数学

和为 s 的连续正数序列（求和公式 / 滑动窗口，清晰图解）

当确定左边界和 target 时，可以通过求根公式得到右边界（去掉负根）；
当右边界为整数时得到一组解；

Python

class Solution:
    def findContinuousSequence(self, target: int):
        i, j, res = 1, 2, []
        while i < j:
            # 当确定左边界和 target 时，可以通过求根公式得到右边界（去掉负根）
            j = (-1 + (1 + 4 * (2 * target + i * i - i)) ** 0.5) / 2
            # 当 j 为整数时得到一组解
            if i < j and j == int(j):
                res.append(list(range(i, int(j) + 1)))
            i += 1
        return res

`剑指Offer 5801 翻转单词顺序 (简单, 2022-01)`

问题简述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
"  I  am a  student. " -> "student. a am I"

详细描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例 1：
    输入: "the sky is blue"
    输出: "blue is sky the"
示例 2：
    输入: "  hello world!  "
    输出: "world! hello"
    解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
    输入: "a good   example"
    输出: "example good a"
    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：
    无空格字符构成一个单词。
    输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：双指针（面试推荐写法）

手写 split 函数，切分字符串，再逆序拼接

Python

class Solution:
    def reverseWords(self, s: str) -> str:

        ret = []
        l, r = 0, 0
        while r < len(s):
            while r < len(s) and s[r] == ' ':  # 跳过空格
                r += 1
            
            l = r  # 单词首位
            while r < len(s) and s[r] != ' ':  # 跳过字符
                r += 1

            if l < r:  # 如果存在字符
                ret.append(s[l: r])

        return ' '.join(ret[::-1])

思路2：库函数

Python

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(s.split()[::-1])

`牛客 0022 合并两个有序的数组 (中等, 2022-01)`

问题简述

给定两个有序数组 A 和 B，请将数组 B 合并到数组 A 中；
A 和 B 中初始的元素数目分别为 m 和 n，A 的数组空间大小为 m + n；
要求不使用额外空间。

合并两个有序的数组_牛客题霸_牛客网

思路

双指针 + 逆序填空；

Python

#
# 
# @param A int整型一维数组 
# @param B int整型一维数组 
# @return void
#
class Solution:
    def merge(self , A, m, B, n):
        # write code here
        i, j = m - 1, n - 1
        p = m + n - 1
        
        while i >= 0 and j >= 0:
            if A[i] > B[j]:
                A[p] = A[i]
                i -= 1
            else:
                A[p] = B[j]
                j -= 1
            p -= 1
        
        while j >= 0:
            A[p] = B[j]
            j -= 1
            p -= 1

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

技巧-双指针.md

技巧-双指针.md

双指针

Problems

`LeetCode 0005 最长回文子串 (中等, 2021-10)`

`LeetCode 0011 盛最多水的容器 (中等, 2021-10)`

`LeetCode 0015 三数之和 (中等, 2021-10)`

`LeetCode 0016 最接近的三数之和 (中等, 2021-10)`

`LeetCode 0042 接雨水 (困难, 2021-10)`

`LeetCode 0167 两数之和2(输入有序数组) (简单, 2021-10)`

`LeetCode 0611 有效三角形的个数 (中等, 2021-10)`

`剑指Offer 2100 调整数组顺序使奇数位于偶数前面 (简单, 2021-11)`

`剑指Offer 4800 最长不含重复字符的子字符串 (中等, 2021-12)`

`剑指Offer 5701 和为s的两个数字 (简单, 2022-01)`

`剑指Offer 5702 和为s的连续正数序列 (简单, 2022-01)`

`剑指Offer 5801 翻转单词顺序 (简单, 2022-01)`

`牛客 0022 合并两个有序的数组 (中等, 2022-01)`

Files

技巧-双指针.md

Latest commit

History

技巧-双指针.md

File metadata and controls

双指针

Problems

LeetCode 0005 最长回文子串 (中等, 2021-10)

LeetCode 0011 盛最多水的容器 (中等, 2021-10)

LeetCode 0015 三数之和 (中等, 2021-10)

LeetCode 0016 最接近的三数之和 (中等, 2021-10)

LeetCode 0042 接雨水 (困难, 2021-10)

LeetCode 0167 两数之和2(输入有序数组) (简单, 2021-10)

LeetCode 0611 有效三角形的个数 (中等, 2021-10)

剑指Offer 2100 调整数组顺序使奇数位于偶数前面 (简单, 2021-11)

剑指Offer 4800 最长不含重复字符的子字符串 (中等, 2021-12)

剑指Offer 5701 和为s的两个数字 (简单, 2022-01)

剑指Offer 5702 和为s的连续正数序列 (简单, 2022-01)

剑指Offer 5801 翻转单词顺序 (简单, 2022-01)

牛客 0022 合并两个有序的数组 (中等, 2022-01)

`LeetCode 0005 最长回文子串 (中等, 2021-10)`

`LeetCode 0011 盛最多水的容器 (中等, 2021-10)`

`LeetCode 0015 三数之和 (中等, 2021-10)`

`LeetCode 0016 最接近的三数之和 (中等, 2021-10)`

`LeetCode 0042 接雨水 (困难, 2021-10)`

`LeetCode 0167 两数之和2(输入有序数组) (简单, 2021-10)`

`LeetCode 0611 有效三角形的个数 (中等, 2021-10)`

`剑指Offer 2100 调整数组顺序使奇数位于偶数前面 (简单, 2021-11)`

`剑指Offer 4800 最长不含重复字符的子字符串 (中等, 2021-12)`

`剑指Offer 5701 和为s的两个数字 (简单, 2022-01)`

`剑指Offer 5702 和为s的连续正数序列 (简单, 2022-01)`

`剑指Offer 5801 翻转单词顺序 (简单, 2022-01)`

`牛客 0022 合并两个有序的数组 (中等, 2022-01)`