https://leetcode-cn.com/tag/two-pointers/
题目汇总
3. 无重复字符的最长子串中等
11. 盛最多水的容器中等
15. 三数之和中等
16. 最接近的三数之和中等
18. 四数之和中等
19. 删除链表的倒数第N个节点中等
26. 删除排序数组中的重复项简单
27. 移除元素简单
28. 实现 strStr()简单（ ？）
30. 串联所有单词的子串困难（？？？）
3. 无重复字符的最长子串中等
给定一个字符串，请你找出其中不含有重复字符的 **最长子串 **的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是"abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是"b"，所以其长度为 1。
思路：双指针的滑动窗口+HashMap
使用HashMap来存储已经遍历过的字符，key为字符，value为字符下标。
使用指针start来标记无重复子串开始下标，end为当前遍历字符下标。
遍历字符串，判断当前字符是否已经在 map 中存在，如果存在则更新无重复子串开始下标 start 为相同字符的下一位置，此时从 start 到 end 为最新的无重复子串，更新结果值；如果不存在则将当前字符与下标放入 map 中。
class Solution {//执行用时 :8 ms, 在所有 Java 提交中击败了71.15%的用户
public int lengthOfLongestSubstring(String s) {
if(s.length()==0)
return 0;
HashMap<Character, Integer> map = new HashMap<>();
int start = 0;
int end = 0;
int result = 0;
for(;start<s.length()&&end<s.length();end++){
if(map.containsKey(s.charAt(end))){
start = Math.max(start, map.get(s.charAt(end))+1);
}
map.put(s.charAt(end),end);
result = Math.max(result, end-start+1);
}
return result;
}
}
11. 盛最多水的容器中等
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
思路：双指针
每次以双指针为左右边界（也就是「数组」的左右边界）计算出的容量中的最大值。移动指向较短线段的指针尽管造成了矩形宽度的减小，但却可能会有助于面积的增大。因为移动较短线段的指针会得到一条相对较长的线段，这可以克服由宽度减小而引起的面积减小。
class Solution {//执行用时 :4 ms, 在所有 Java 提交中击败了73.78%
public int maxArea(int[] height) {
if(height.length == 0)
return 0;
int left = 0;
int 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;
}
}
15. 三数之和中等
给你一个包含 n 个整数的数组
nums，判断nums中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路：排序+双指针
遍历排序后数组：
设置左右指针，当 left<right 时，执行循环：
当 sum=0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 left，right 移到下一位置，寻找新的解。
若sum>0 ，说明 nums[right]太大，right 左移；
若sum<0， 说明 nums[left] 太小，left 右移。
class Solution {//执行用时 :22 ms, 在所有 Java 提交中击败了94.86%的用户
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length <= 2)
return res;
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i] > 0)
return res;//因为已经排好序，此时不可能等于0，直接返回结果集
if(i > 0 && nums[i]==nums[i-1])
continue;//遇到相同元素跳过
int left = i + 1;
int right = nums.length - 1;
while(left < right){
int sum = nums[left] + nums[i] + nums[right];
if(sum == 0){
res.add(Arrays.asList(nums[left],nums[i],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 > 0){
right--;
}
else{
left++;
}
}
}
return res;
}
}
16. 最接近的三数之和中等
给定一个包括 n个整数的数组
nums和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. 因为(-1 + 2 + 1 = 2).
思路：排序+双指针，时间复杂度O(n*n)
和上道题目类似
class Solution {//执行用时 :6 ms, 在所有 Java 提交中击败了86.74%的用户
public int threeSumClosest(int[] nums, int target) {
if(nums == null || nums.length < 3)
return 0;
Arrays.sort(nums);
int ans = nums[0] + nums[1] + nums[2];
for(int i=0;i<nums.length;i++){
int left = i + 1;
int right = nums.length - 1;
while(left < right){
int sum = nums[left] + nums[i] +nums[right];
if(Math.abs(target - sum) < Math.abs(target - ans))
ans = sum;
if(sum < target)
left++;
else if(sum > target)
right--;
else
return ans;
}
}
return ans;
}
}
18. 四数之和中等
给定一个包含 n 个整数的数组
nums和一个目标值target，判断nums中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与target相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
思路：排序+双指针
和三数之和的思路一样，增加一层循环即可
class Solution {//执行用时 :31 ms, 在所有 Java 提交中击败了20.81%的用户
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
if(nums == null || nums.length < 4)
return res;
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(i>0 && nums[i]==nums[i-1])
continue;
if(j>i+1 && nums[j] == nums[j-1])
continue;
int left = j+1;
int right = nums.length-1;
while(left<right){
int sum = nums[left]+nums[i]+nums[j]+nums[right];
if(sum == target){
res.add(Arrays.asList(nums[left],nums[i],nums[j],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)
right--;
else
left++;
}
}
}
return res;
}
}
19. 删除链表的倒数第N个节点中等
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？
思路：双指针
设置快慢指针，快指针先移动n步，然后快慢指针一起移动，知道快指针指向最后一个节点，慢指针指向要删除的节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
//第一个指针先指向第(l-n+2)个结点，即要删除的结点的前一个结点
while(n != 0){
first = first.next;
n--;
}
//两个指针一起移动，第二个指针指向要删除的结点
while(first.next != null){
first = first.next;
second = second.next;
}
//此时删除结点
second.next = second.next.next;
return dummy.next;
}
}
26. 删除排序数组中的重复项简单
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，并在使用 O(1) 额外空间的条件下完成。
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为1,2。 你不需要考虑数组中超出新长度后面的元素。
思路：双指针，时间复杂度：O(n)
用 2 个指针，一个i在前，一个j在后，比较 i 和 j 位置的元素是否相等。
如果相等，j 后移 1 位；如果不相等，将 j 位置的元素复制到 i+1 位置上，i 后移一位，j 后移 1 位。重复上述过程，直到 j 等于数组长度。
返回 i + 1，即为新数组长度。
class Solution {//执行用时 :1 ms, 在所有 Java 提交中击败了98.65%的用户
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length < 1)
return 0;
int i = 0;
int j = 1;
while(j < nums.length){
if(nums[i] != nums[j]){
nums[i+1] = nums[j];
i++;
}
j++;
}
return i+1;
}
}
27. 移除元素简单
给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组**。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
给定 nums = [3,2,2,3], val = 3,函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
思路：双指针，时间复杂度：O(n)
用 2 个指针，其中 i 是慢指针，j是快指针。当 nums[j]与给定的值相等时，递增 j 以跳过该元素。只要 nums[j]!=val，我们就复制 nums[j] 到 nums[i] 并同时递增两个索引。重复这一过程，直到 j 到达数组的末尾，该数组的新长度为 i。
class Solution {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
public int removeElement(int[] nums, int val) {
if(nums == null || nums.length == 0)
return 0;
int i = 0;
int j = 0;
while(j<nums.length){
if(nums[j]!=val){
nums[i]=nums[j];
i++;
}
j++;
}
return i;
}
}
28. 实现 strStr()简单
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
思路：双指针
来自官方题解方法二https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode/
class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了41.29%的用户
public int strStr(String haystack, String needle) {
int L = needle.length();
int n = haystack.length();
if (L == 0) return 0;
int pn = 0;
while (pn < n - L + 1) {
//在haystack字符串中，找到第一个needle字符的位置
while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0))
++pn;
//计算最大匹配字符串
int currLen = 0, pL = 0;
while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
++pn;
++pL;
++currLen;
}
//如果整个needle字符串被找到，返回它的开始位置
if (currLen == L)
return pn - L;
//否则回溯
pn = pn - currLen + 1;
}
return -1;
}
}
30. 串联所有单词的子串困难
给定一个字符串 s和一些长度相同的单词 words。找出 s中恰好可以由 words中所有单词串联形成的子串的起始位置。
注意子串要与 words中的单词完全匹配，中间不能有其他字符，但不需要考虑 words中单词串联的顺序。
示例 1：
输入：
s = "barfoothefoobarman",words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：
s = "wordgoodgoodgoodbestword",words = ["word","good","best","word"]
输出：[]
网友评论