• 基础知识：常见双指针算法分为三类，同向（即两个指针都相同一个方向移动），背向（两个指针从相同或者相邻的位置出发，背向移动直到其中一根指针到达边界为止），相向（两个指针从两边出发一起向中间移动直到两个指针相遇）
• 背向双指针：(基本上全是回文串的题)

Leetcode 409. Longest Palindrome

Leetcode 125. Valid Palindrome

Leetcode 5. Longest Palindromic Substring

Leetcode 647. Palindromic Substrings

• 相向双指针：(以two sum为基础的一系列题)

Leetcode 1. Two Sum (这里使用的是先排序的双指针算法，不同于hashmap做法)

Leetcode 167. Two Sum II - Input array is sorted

Leetcode 15. 3Sum

Leetcode 16. 3Sum Closest

Leetcode 18. 4Sum

Leetcode 454. 4Sum II

Leetcode 277. Find the Celebrity

Leetcode 11. Container With Most Water

• 同向双指针：（个人觉得最难的一类题，可以参考下这里 TimothyL：Leetcode 同向双指针/滑动窗口类代码模板）

Leetcode 283. Move Zeroes

Leetcode 26. Remove Duplicate Numbers in Array

Leetcode 395. Longest Substring with At Least K Repeating Characters

Leetcode 340. Longest Substring with At Most K Distinct Characters

Leetcode 424. Longest Repeating Character Replacement Leetcode 76. Minimum Window Substring

Leetcode 3. Longest Substring Without Repeating Characters

Leetcode 1004 Max Consecutive Ones III

Leetcode 409. Longest Palindrome

题目描述

给定一个包含大写字母和小写字母的字符串 s ，找出至少包含 s 中的一个字母的最长回文串。

示例 1:

输入: "abccccdd" 输出: 7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

解法

本题的解法可以使用哈希表来统计每个字符出现的次数。对于每个字符出现的次数，如果是偶数，则直接加入回文串；如果是奇数，则将其减一后加入回文串。最后，如果存在出现次数为奇数的字符，可以将其放在回文串中间。

代码

java

class Solution {
    public int longestPalindrome(String s) {
        int[] count = new int[128];
        for (char c : s.toCharArray()) {
            count[c]++;
        }
        int length = 0;
        boolean hasOdd = false;
        for (int i : count) {
            if (i % 2 == 0) {
                length += i;
            } else {
                length += i - 1;
                hasOdd = true;
            }
        }
        return hasOdd ? length + 1 : length;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串并统计每个字符出现的次数，时间复杂度为 O(n)。

空间复杂度：O(1)。由于字符集大小为 O(1)，因此需要使用大小为 O(1) 的数组存储每个字符出现的次数。

Leetcode 125. Valid Palindrome

题目描述

给定一个字符串，判断它是否是回文串，只考虑字母和数字字符，忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1： 输入: "A man, a plan, a canal: Panama" 输出: true

示例 2： 输入: "race a car" 输出: false

提示： 1 <= s.length <= 2 * 10^5 字符串 s 由 ASCII 字符组成

解法

本题的解法是使用双指针。首先将字符串转换成小写，然后使用双指针分别指向字符串头部和尾部，比较两个指针所指的字符是否相等，若不相等则返回 false，否则将指针向中间移动，直到两个指针相遇。

需要注意的是，只考虑字母和数字字符，需要使用 Character.isLetterOrDigit(char c) 方法进行判断。

代码

java

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        s = s.toLowerCase();
        int left = 0, right = s.length() - 1;
        while (left < right) {
            char c1 = s.charAt(left), c2 = s.charAt(right);
            if (!Character.isLetterOrDigit(c1)) {
                left++;
            } else if (!Character.isLetterOrDigit(c2)) {
                right--;
            } else if (c1 != c2) {
                return false;
            } else {
                left++;
                right--;
            }
        }
        return true;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。最坏情况下需要比较字符串的所有字符。 空间复杂度：O(1)。只使用了常数级别的额外空间。

Leetcode 5. Longest Palindromic Substring

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd" 输出: "bb"

解法

本题可以使用中心扩展算法或者动态规划算法来解决。

1. 中心扩展算法

对于一个回文串，如果它的长度为奇数，那么它的中心只有一个字符；如果它的长度为偶数，那么它的中心是两个相邻的字符。

因此，我们可以从每个字符和每对相邻字符开始，向两边扩展，直到遇到不同的字符为止，此时回文串的长度即为扩展的长度减一。

具体实现时，我们需要考虑字符串长度为奇偶的情况，以及回文串长度为1和2的情况。

2. 动态规划算法

我们定义 $dp[i][j]dp[i][j]$ 表示字符串从 $ii$ 到 $jj$ 是否为回文串，如果是，则 $dp[i][j]=truedp[i][j]=true$，否则 $dp[i][j]=falsedp[i][j]=false$。

对于一个子串，如果它是回文串，并且它的左右两个字符也相等，则它的左右两个子串也一定是回文串。

因此，我们可以从小到大枚举子串的长度 $lenlen$，从左至右枚举子串的起始位置 $ii$，并用 $j=i+len-1j=i+len-1$ 表示子串的结束位置，状态转移方程为：

其中 $(s_i==s_j)(s\_i==s\_j)$ 表示当前子串的左右两个字符相等， 表示子串长度小于等于2，$dp[i+1][j-1]dp[i+1][j-1]$ 表示左右两个子串也是回文串。

最终的答案即为长度最长的回文串。

代码

中心扩展算法

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int maxLen = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                start = i - (len - 1) / 2;
            }
        }
        return s.substring(start, start + maxLen);
    }

    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

动态规划算法

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1;
        int start = 0;
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    if (len <= 2 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (len > maxLen) {
                            maxLen = len;
                            start = i;
                        }
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }
}

复杂度分析

中心扩展算法

时间复杂度：$O(n^2)O(n^2)$，其中 $nn$ 是字符串的长度。最坏情况下，回文中心在每个字符之间，共有 $2n-12n-1$ 个回文中心，每个中心最多需要扩展 $n\mathrm{/}2n/2$ 次。

空间复杂度：$O(1)O(1)$。

动态规划算法

时间复杂度：$O(n^2)O(n^2)$，其中 $nn$ 是字符串的长度。状态转移方程需要 $O(1)O(1)$ 的时间计算，共有 $n^{2}n^2$ 个状态需要计算。

空间复杂度：$O(n^2)O(n^2)$，需要存储所有状态。

Leetcode 647. Palindromic Substrings

题目描述

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1： 输入："abc" 输出：3 解释：三个回文子串: "a", "b", "c"

示例 2： 输入："aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示： 输入的字符串长度不会超过 1000 。

解法

本题可以采用中心扩展法来做。对于一个回文子串，它要么是奇数长度，要么是偶数长度。因此，我们可以从字符串的每一个字符开始，分别以它为中心向两边扩展，找到所有以该字符为中心的回文子串；然后再以该字符和下一个字符的间隙为中心，向两边扩展，找到所有以该间隙为中心的回文子串。

代码

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < 2 * n - 1; i++) {
            int l = i / 2, r = l + i % 2;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                ans++;
                l--;
                r++;
            }
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 是字符串的长度。需要枚举每一个中心，每个中心最多会向外扩展 O(n) 次。

空间复杂度：O(1)。除了常数变量以外，空间复杂度是常数。

Leetcode 1. Two Sum (这里使用的是先排序的双指针算法，不同于hashmap做法)

题目描述

给定一个整数数组 nums 和一个整数目标值 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 <= 105
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

解法

先将数组排序，然后使用双指针算法。定义两个指针，一个指向数组的起始位置，一个指向数组的末尾位置。如果两个指针指向的元素之和等于目标值，则返回它们的下标；如果它们之和小于目标值，则将左指针往右移动一位；如果它们之和大于目标值，则将右指针往左移动一位。重复上述操作直到找到答案。

时间复杂度：O(nlogn)，其中 n 是数组的长度。排序的时间复杂度是 O(nlogn)，双指针算法的时间复杂度是 O(n)。

空间复杂度：O(n)，其中 n 是数组的长度。需要额外使用一个数组来存储排序后的数组。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        int[] sorted = Arrays.copyOf(nums, n);
        Arrays.sort(sorted);
        int left = 0, right = n - 1;
        while (left < right) {
            int sum = sorted[left] + sorted[right];
            if (sum == target) {
                break;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        int index1 = -1, index2 = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == sorted[left] && index1 == -1) {
                index1 = i;
            } else if (nums[i] == sorted[right] && index2 == -1) {
                index2 = i;
            }
        }
        return new int[]{index1, index2};
    }
}

复杂度分析

时间复杂度：O(nlogn)，其中 n 是数组的长度。排序的时间复杂度是 O(nlogn)，双指针算法的时间复杂度是 O(n)。

空间复杂度：O(n)，其中 n 是数组的长度。需要额外使用一个数组来存储排序后的数组。

Leetcode 167. Two Sum II - Input array is sorted

题目描述

给定一个已按照 升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

• 返回的下标值（index1 和 index2）不是从零开始的。
• 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例 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 <= nums.length <= 3 * 10^4
• -1000 <= nums[i] <= 1000
• nums 按 递增顺序 排列
• -1000 <= target <= 1000

解法

使用双指针方法，定义左指针left指向数组的第一个元素，右指针right指向数组的最后一个元素，计算左右指针所指元素之和sum，如果sum等于目标数target，则返回left+1和right+1；如果sum小于target，则left指针右移；如果sum大于target，则right指针左移。重复以上操作，直到找到符合要求的结果。

代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

复杂度分析

时间复杂度：O(n)，其中n为数组的长度。两个指针移动的总次数最多为n次。

空间复杂度：O(1)。只需要常数级别的空间存储left、right、sum等变量。

Leetcode 15. 3Sum

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 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

解法

本题的解法是首先将数组排序，然后枚举第一个数，再使用双指针的方法，去寻找另外两个数。如果三个数的和小于 0，则将左指针右移，如果大于 0，则将右指针左移。如果等于 0，则将结果添加到答案中。需要注意的是，如果枚举到的数大于 0，则三数之和一定大于 0，结束循环。另外，如果数组中有重复的数字，则可能会出现重复解，但我们只需要使用哈希表去重即可。

代码

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        if (nums == null || len < 3) {
            return ans;
        }
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if (nums[i] > 0) {
                break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            }
            if (i > 0 && nums[i] == nums[i-1]) {
                continue; // 去重
            }
            int L = i+1;
            int R = len-1;
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) {
                        L++; // 去重
                    }
                    while (L<R && nums[R] == nums[R-1]) {
                        R--; // 去重
                    }
                    L++;
                    R--;
                } else if (sum < 0) {
                    L++;
                } else if (sum > 0) {
                    R--;
                }
            }
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。排序的时间复杂度是 O(nlogn)，枚举三元组的时间复杂度是 O(n^2)，因此总时间复杂度为 O(nlogn+n^2)=O(n^2)。

空间复杂度：O(logn)。排序需要使用 O(logn) 的空间。然而我们忽略这一项的空间复杂度。最后返回值的空间复杂度为 O(C(n,3))，即答案的空间复杂度。为 O(n^3)。

Leetcode 16. 3Sum Closest

题目描述

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

示例 1：

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

示例 2：

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

提示：

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

解法

本题解法与15题类似，先将数组排序，然后使用双指针法遍历数组，寻找三个数的和与目标值最接近的情况。具体实现时，使用一个变量记录当前最小差距，以及一个变量记录对应的三个数的和。

时间复杂度：O(n^2)

空间复杂度：O(1)

代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int closestSum = nums[0] + nums[1] + nums[2];
        int minDiff = Math.abs(closestSum - target);
        for (int i = 0; i < n; i++) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                int diff = Math.abs(sum - target);
                if (diff < minDiff) {
                    minDiff = diff;
                    closestSum = sum;
                }
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    return target;
                }
            }
        }
        return closestSum;
    }
}

复杂度分析

时间复杂度：O(n^2)

空间复杂度：O(1)

Leetcode 18. 4Sum

题目描述

给定一个包含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

解法

本题可以先将数组排序，然后使用双指针法和夹逼的思想，在排序后的数组中找到所有的四元组，使得它们的和等于目标值。

具体的实现方法是，先枚举前两个数，然后使用双指针法在剩下的数中找到后两个数，使得四个数的和等于目标值。在枚举前两个数和找后两个数的过程中，需要注意去重的问题。

代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
                    continue;
                }
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度：O(n^3)，其中 n 是数组的长度。排序的时间复杂度是 O(nlogn)，枚举四元组的时间复杂度是 O(n^3)，因此总时间复杂度是 O(nlogn+n^3)=O(n^3)。

空间复杂度：O(logn)，排序需要使用 O(logn) 的栈空间。

Leetcode 454. 4Sum II

题目描述

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A、B、C、D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

示例：

输入： A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2]

输出： 2

解释： 两个元组如下：

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解法

本题可以使用哈希表来解决，将 A 和 B 数组的所有元素两两相加，得到所有可能的和及其出现的次数，然后再遍历 C 和 D 数组，将它们两两相加的结果取反后，在哈希表中查找是否存在这个数，如果存在，就将对应的出现次数加入答案中。

代码

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int a : A) {
            for (int b : B) {
                int sum = a + b;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        int res = 0;
        for (int c : C) {
            for (int d : D) {
                int sum = -(c + d);
                res += map.getOrDefault(sum, 0);
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n 是数组的长度。需要遍历 A 和 B 数组，时间复杂度是 O(n^2)，遍历 C 和 D 数组，时间复杂度是 O(n^2)，因此总时间复杂度是 O(n^2)。

空间复杂度：O(n^2)，其中 n 是数组的长度。哈希表中存储 A 和 B 数组的所有元素两两相加的和及其出现的次数，需要 O(n^2) 的空间。

Leetcode 277. Find the Celebrity

题目描述

假设你是一个专业的狗仔，参加了一个 n 人派对，其中每个人被从 0 到 n - 1 标号。在这个派对人群当中可能存在一位 “名人”。所谓 “名人” 的定义是：其他所有 n - 1 个人都认识他/她，而他/她并不认识其他任何人。

现在你想要确认这个 “名人” 是谁，或者确定这里没有 “名人”。而你唯一能做的就是问诸如 “A 你好呀，请问你认不认识 B？” 的问题，以此来确定 A 是否认识 B。你需要找到这个 “名人”（如果存在）并返回他/她的编号；如果不存在 “名人”，则返回 -1。

示例 1：

输入: graph = [ [1,1,0], [0,1,0], [1,1,1] ] 输出: 1 解释: 人物编号为 1 的人是名人，因为 0 和 2 都认识他/她，但是 1 不认识其他人。

示例 2：

输入: graph = [ [1,0,1], [1,1,0], [0,1,1] ] 输出: -1 解释: 没有名人。

提示：

• n == graph.length
• n == graph[i].length
• 2 <= n <= 100
• graph[i][j] 是 0 或 1。
• graph[i][i] == 1

解法

本题的解法是使用两个指针，一个指向第一个人，另一个指向第二个人。根据题目的定义，如果第一个人认识第二个人，则第一个人不可能是名人；如果第一个人不认识第二个人，则第二个人不可能是名人。因此，在每次比较后，我们都可以排除一个人，直到只剩下一个人为止。最后，我们再验证这个人是否真的是名人。

具体来说，我们定义两个指针 i 和 j，初始时分别指向第一个人。然后，我们每次对 i 和 j 进行如下操作：

• 如果 i 认识 j，则将 i 移动到下一个人，即 i=i+1。
• 如果 i 不认识 j，则将 j 移动到下一个人，即 j=j+1。

最后，我们验证指针 i 是否是名人即可。

需要注意的是，由于题目保证了“其他所有 n - 1 个人都认识他/她”，所以我们只需要在验证时判断 i 是否认识所有其他人即可。

代码

public class Solution extends Relation {
    public int findCelebrity(int n) {
        int i = 0, j = 1;
        while (j < n) {
            if (knows(i, j)) {
                i = j;
            }
            j++;
        }
        for (int k = 0; k < n; k++) {
            if (k != i && (knows(i, k) || !knows(k, i))) {
                return -1;
            }
        }
        return i;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是人数。在第一次循环中，我们最多会比较 n-1 次。在验证阶段，我们最多需要再比较 n-1 次。

空间复杂度：O(1)。我们只需要常数空间存储两个指针。

Leetcode 11. Container With Most Water

题目描述

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

说明： 你不能倾斜容器，且 n 的值至少为 2。

示例 1：

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

示例 2：

输入：height = [1,1] 输出：1

示例 3：

输入：height = [4,3,2,1,4] 输出：16

示例 4：

输入：height = [1,2,1] 输出：2

提示：

• n = height.length
• 2 <= n <= 3 * 104
• 0 <= height[i] <= 3 * 104

解法

本题的解法是使用双指针，从数组两端向中间移动，计算每个位置的面积，取最大值。

具体来说，定义两个指针 left 和 right，分别指向数组的最左端和最右端。每次计算 left 和 right 之间的面积，并将面积最大值更新。然后判断 height[left] 和 height[right] 的大小，将较小的值所在的指针向中间移动一位。

为什么这种方法是正确的呢？因为容器的面积受到两个因素的影响，即底边的长度和两个端点的高度。如果将较高的那个端点所在的指针向中间移动，那么底边的长度一定会减少。因此，为了使面积最大化，我们应该将较小的那个端点所在的指针向中间移动，以期望能够遇到更高的端点。

代码

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。双指针总共最多移动 n−1 次。

空间复杂度：O(1)。只需要常数级别的额外空间。

Leetcode 283. Move Zeroes

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

说明:

• 必须在原数组上操作，不能拷贝额外的数组。
• 尽量减少操作次数。

解法

本题的解法是使用双指针，一个指针用于遍历数组，另一个指针用于记录非零元素的位置。遍历过程中，如果当前元素不为0，则将其与非零元素位置的元素交换，并将非零元素位置指针加1。最后，将非零元素位置之后的元素全部赋值为0即可。

代码

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
            }
            right++;
        }
        for (int i = left; i < n; i++) {
            nums[i] = 0;
        }
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。双指针遍历一遍数组，时间复杂度为 O(n)。

空间复杂度：O(1)。只需要使用常数级别的额外空间。

Leetcode 26. Remove Duplicate Numbers in Array

题目描述

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以 “引用” 方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解法

本题的解法是双指针法，使用两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。

当我们遇到 nums[j] != nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i+1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。

代码

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。快指针最多遍历一次数组，慢指针最多遍历一次数组，因此总时间复杂度为 O(n)。

空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

Leetcode 395. Longest Substring with At Least K Repeating Characters

题目描述

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1： 输入：s = "aaabb", k = 3 输出：3 解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2： 输入：s = "ababbc", k = 2 输出：5 解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

提示： 1 <= s.length <= 10^4 s 仅由小写英文字母组成 1 <= k <= 10^5

解法

本题可以使用分治法进行解答。首先统计字符串中每个字符出现的次数，然后找到字符串中出现次数小于 k 的字符，将其作为分割点，将原字符串分为若干子串。对于每个子串，递归处理，返回其中的最长子串的长度。最后将所有子串的最长子串长度取最大值即可。

代码

class Solution {
    public int longestSubstring(String s, int k) {
        int n = s.length();
        int[] cnt = new int[26];
        for (int i = 0; i < n; i++) {
            cnt[s.charAt(i) - 'a']++;
        }

        boolean flag = true;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0 && cnt[i] < k) {
                flag = false;
                char c = (char)('a' + i);
                String[] strs = s.split(String.valueOf(c));
                int res = 0;
                for (String str : strs) {
                    res = Math.max(res, longestSubstring(str, k));
                }
                return res;
            }
        }

        if (flag) {
            return n;
        }
        return 0;
    }
}

复杂度分析

时间复杂度：O(nlogn)，其中 n 是字符串的长度。分治的时间复杂度为O(logn)，每次递归处理的时间复杂度为O(n)。

空间复杂度：O(logn)，递归栈的深度为O(logn)。

Leetcode 340. Longest Substring with At Most K Distinct Characters

题目描述

给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。

示例 1:

输入: s = "eceba", k = 2 输出: 3 解释: 则 T 为 "ece" ，所以长度为 3。

示例 2:

输入: s = "aa", k = 1 输出: 2 解释: 则 T 为 "aa" ，所以长度为 2。

提示:

1 <= s.length <= 5 * 104 0 <= k <= 50

解法

本题的解法是使用滑动窗口。使用两个指针 left 和 right 分别表示子串的左右边界，使用一个哈希表 map 存储当前子串中每个字符出现的次数。当哈希表中不同字符的数量小于等于 k 时，右指针 right 向右移动，同时更新哈希表中对应字符的出现次数。当哈希表中不同字符的数量大于 k 时，左指针 left 向右移动，同时更新哈希表中对应字符的出现次数。每次移动指针时，都需要更新最长子串的长度。

代码

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) {
            return 0;
        }
        int left = 0, right = 0, maxLen = Integer.MIN_VALUE;
        Map<Character, Integer> map = new HashMap<>();
        while (right < s.length()) {
            char c = s.charAt(right);
            map.put(c, map.getOrDefault(c, 0) + 1);
            while (map.size() > k) {
                char d = s.charAt(left);
                int count = map.get(d);
                if (count == 1) {
                    map.remove(d);
                } else {
                    map.put(d, count - 1);
                }
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
            right++;
        }
        return maxLen;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串一次，每次遍历的时间复杂度是 O(1)。

空间复杂度：O(k)，其中 k 是不同字符的数量。最坏情况下，哈希表中会存储 k 个字符，因此空间复杂度是 O(k)。

Leetcode 424. Longest Repeating Character Replacement

题目描述

给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。

示例 1:

输入: s = "eceba", k = 2 输出: 3 解释: 则 T 为 "ece"，所以长度为 3。

示例 2:

输入: s = "aa", k = 1 输出: 2 解释: 则 T 为 "aa"，所以长度为 2。

提示:

1 <= s.length <= 10^4 s 仅由小写英文字母组成 1 <= k <= 10^5

解法

本题的解法是使用滑动窗口。维护一个窗口，使得窗口内包含的不同字符数不超过 k。如果窗口内不同字符数超过了 k，则将窗口左端点右移，直到不同字符数小于等于 k。

代码

class Solution {
    public int characterReplacement(String s, int k) {
        int[] count = new int[26];
        int left = 0, right = 0, maxCount = 0, maxLength = 0;
        while (right < s.length()) {
            count[s.charAt(right) - 'A']++;
            maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
            right++;
            if (right - left > maxCount + k) {
                count[s.charAt(left) - 'A']--;
                left++;
            }
            maxLength = Math.max(maxLength, right - left);
        }
        return maxLength;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串一次，并且维护滑动窗口的时间复杂度为 O(1)。

空间复杂度：O(1)。我们需要维护一个长度为 26 的数组，它存储了每个字符出现的次数。由于字符集大小为固定的 26，因此空间复杂度为 O(1)。

Leetcode 76. Minimum Window Substring

题目描述

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"

说明： 如果 S 中不存这样的子串，则返回空字符串 ""。 如果 S 中存在这样的子串，我们保证它是唯一的答案。

解法

本题可以使用滑动窗口的思想进行求解。

我们使用两个指针 left 和 right，表示滑动窗口的左右边界，先将 left 和 right 都初始化为 0。然后我们先移动 right，直到滑动窗口中包含了 T 中的所有字符。然后再移动 left，直到滑动窗口中不再包含 T 中的所有字符。这时候我们记录下此时的滑动窗口长度，并将 left 和 right 继续向右移动，直到 right 到达字符串 S 的末尾。

在移动 right 和 left 的过程中，我们可以使用一个 HashMap 来记录滑动窗口中每个字符出现的次数。当我们移动 right 时，将 right 对应的字符出现次数加一；当我们移动 left 时，将 left 对应的字符出现次数减一。当某个字符的出现次数等于 T 中该字符出现次数时，表示滑动窗口中已经包含了该字符。

代码

class Solution {
    public String minWindow(String s, String t) {
        // 统计 t 中每个字符出现的次数
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        // 定义滑动窗口左右边界和计数器
        int left = 0, right = 0, count = map.size();
        // 定义最小子串的左右边界和长度
        int start = 0, end = 0, len = Integer.MAX_VALUE;
        // 遍历字符串 s
        while (right < s.length()) {
            char c = s.charAt(right);
            // 当前字符在 t 中出现过
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                // 当前字符在 t 中出现次数已经满足要求
                if (map.get(c) == 0) {
                    count--;
                }
            }
            right++;
            // 当前滑动窗口包含了 t 中所有字符
            while (count == 0) {
                // 更新最小子串的左右边界和长度
                if (right - left < len) {
                    start = left;
                    end = right;
                    len = right - left;
                }
                char ch = s.charAt(left);
                // 当前字符在 t 中出现过
                if (map.containsKey(ch)) {
                    map.put(ch, map.get(ch) + 1);
                    // 当前字符在 t 中出现次数不满足要求
                    if (map.get(ch) > 0) {
                        count++;
                    }
                }
                left++;
            }
        }
        // 如果最小子串的长度为 Integer.MAX_VALUE，说明不存在这样的子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, end);
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 S 的长度。因为我们每个字符都只会访问一次，所以时间复杂度是 O(n)。 空间复杂度：O(m)，其中 m 是字符串 T 中不同字符的个数。因为我们需要使用一个 HashMap 来记录滑动窗口中每个字符出现的次数，所以空间复杂度是 O(m)。

Leetcode 3. Longest Substring Without Repeating Characters

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解法

本题可以使用滑动窗口来解决。我们维护一个窗口，用来存储不重复的子串。在遍历字符串的过程中，如果当前字符不在窗口中，则将其加入窗口，更新窗口右边界。如果当前字符在窗口中，则从窗口左边开始删除字符，直到窗口中不再包含当前字符。

在遍历过程中，用一个变量来记录窗口的长度，并不断更新最长子串的长度。

代码

java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度。遍历字符串的时间复杂度是 O(n)，而在遍历过程中，每个字符最多只会被访问一次，所以时间复杂度是 O(n)。

空间复杂度：O(min(m, n))，其中 m 是字符集的大小。在本题中，字符集为所有 ASCII 码在 [0, 128) 内的字符，即 m=128。我们需要用一个集合来存储窗口中的字符，而集合的大小最多为字符集的大小，所以空间复杂度是 O(min(m, n))。

Leetcode 1004 Max Consecutive Ones III

题目描述

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

 

示例 1：

输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释： [1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：A = [0,0,0,1,1,1,0,0,0,1,1,1,1,1], K = 2 输出：6 解释： [0,0,0,1,1,1,1,1,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。

 

提示：

1 <= A.length <= 20000 0 <= K <= A.length A[i] 为 0 或 1 

解法

本题可以使用滑动窗口的方法来解决。

我们可以维护一个左指针和右指针，初始时均指向数组的起始位置。

然后我们让右指针不断向右移动，每次移动时，如果当前位置为 0，则将 K 的值减 1。

当 K 的值小于 0 时，说明我们需要将左指针向右移动，同时将左指针所指的位置从 0 变为 1。

当左指针向右移动时，如果左指针所指的位置为 1，则不需要将 K 的值加回来，因为我们只需要维护最长的 1 的子数组长度即可。

最后，我们可以用一个变量来维护最长的 1 的子数组长度，每次更新时取当前长度和之前最长长度的较大值。

代码

class Solution {
    public int longestOnes(int[] A, int K) {
        int left = 0, right = 0;
        int maxLen = 0;
        while (right < A.length) {
            if (A[right] == 0) {
                K--;
            }
            if (K < 0) {
                if (A[left] == 0) {
                    K++;
                }
                left++;
            }
            right++;
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度。我们最多只需要遍历整个数组一次。

空间复杂度：O(1)。我们只需要常数级别的空间来存储左指针和右指针的位置，以及最长的 1 的子数组长度。