LeetCode双指针经典题（一）15道_双指针 题目

905. 按奇偶排序数组

https://leetcode-cn.com/problems/sort-array-by-parity/

使用两个指针，第一个指针从前往后寻找奇数，第二个指针从后往前寻找偶数，找到了就交换，然后分别继续往前往后寻找，直到两个指针相遇

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int n=nums.length;
        int i=0,j=n-1;
        while(i<j)
        {
            while(i<n&&nums[i]%2==0)//找到前面的奇数
                i++;
            while(j>=0&&nums[j]%2==1)//找到后面的偶数
                j--;
            if(i>=j)//寻找完毕
                break;
            int tmp=nums[i];//交换
            nums[i]=nums[j];
            nums[j]=tmp;
            i++;
            j--;
        }
        return nums;
    }
}
//O(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5. 最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

思路：中心拓展法 枚举中心点，然后向两侧拓展 如果两侧指针指向的字符不相等 则停止拓展 中心点可能是1个,比如aba这种以b作为中心点，也可能是2个，比如abba这种以bb为中心点，因此一共有n个单个字符中心点，n-1个双字符中心点（一共2n-1种情况）不需要3字符和4字符中心点，因为它们分别可以从单字符和双字符拓展得到

class Solution {
    public String longestPalindrome(String s) {
        int maxLen=0,n=s.length();
        int start=0;
        for(int i=0;i<2*n-1;i++)
        {
            //i为偶数时  left=right  单中心点
            //i为奇数时  right=left+1  双中心点
            int left=i/2,right=left+i%2;
            while(left>=0&&right<n&&s.charAt(left)==s.charAt(right))
            {
            
                int len=right-left+1;
                if(len>maxLen)//更新最大长度
                {
                    maxLen=len;
                    start=left;//更新起点
                }
                left--;
                right++;    
            }
        } 
        return s.substring(start,start+maxLen);//起点+最大长度确定最长回文子串
    }
}
//O(n)
//O(1)
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

11. 盛最多水的容器

https://leetcode-cn.com/problems/container-with-most-water/

思路：假设左边的线的高度为h1,右边的线的高度为h2, 那么由这两条线所形成的容器可以容纳的水的体积为:min(h1,h2)*(j-i) 即水的体积由短板决定 那么如果继续移动长板，假设h1>h2, h1增加的话，水的体积不变; h1减小的话，水的体积可能减小也可能不变； 移动h2的话，h2增加水的体积增加；h2减小的话，水的体积减小； 所以要想水的体积增大，只有一种可能，就是移动h2(短板)
所以每次移动短板获得新的水的体积，不断更新最大值即可（贪唯一的增加可能性）

class Solution {
    public int maxArea(int[] height) {
        int left=0,right=height.length-1;
        int ans=0;
        while(left<right)
        {
            if(height[left]>height[right])
            {
                ans=Math.max(ans,(right-left)*height[right]);
                right--;
            }
            else
            {
                ans=Math.max(ans,(right-left)*height[left]);
                left++;
            }
        }
        return ans;
    }
}
//O(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

15. 三数之和

https://leetcode-cn.com/problems/3sum/

思路：先对数组按升序排序，排序的好处： 记第一个元素为nums[first], 当nums[first]>0时，则说明后面的元素都大于0，不可能形成a+b+c=0的情况，此时结束循环；相等的元素一定连续在一起，这样利于去重。 具体思路：先固定第一个元素的下标first, first的范围为[0,n-2], 然后需要寻找的目标就是-nums[first], 照nums[second]+nums[third]=target时，可以采用双指针法，left从前往后遍历，right从后往前遍历, 二者之和分为以下3种情况：

1. num[left]+nums[right]=target 找到 添加一个三元组到答案中 left++ right-- 同时进行去重操作
2. num[left]+nums[right]>target 此时right应该左移 使得整体变小
3. num[left]+nums[right]<target 此时left应该右移 使得整体变大

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        if(nums.length<3)
            return ans;
        int n=nums.length;
        Arrays.sort(nums);
        for(int first=0;first<n-2;first++)
        {
            if(nums[first]>0)//后面的元素都大于0了
                break;
            if(first>=1&&nums[first]==nums[first-1])//-1 -1 -1 ....只需要以第一个-1开头就行了
                continue;
            int target=-nums[first];
            int left=first+1,right=n-1;
            while(left<right)
            {
               
                if(nums[left]+nums[right]==target)
                {
                   
                    List<Integer> tmp=new ArrayList<>();
                    tmp.add(nums[first]);
                    tmp.add(nums[left]);
                    tmp.add(nums[right]);
                    ans.add(tmp);
                    left++;
                    right--;
                    while(left<right&&nums[left]==nums[left-1])//-2 0 0 2 2 排除这种重复的情况
                        left++;
                    while(left<right&&nums[right]==nums[right+1])//-2 0 0 2 2 排除这种重复的情况
                        right--;
                    //-2 0 0 2 2只需要一个-2 0 2 当nums[first]=-2  nums[left]=nums[1]=0  nums[right]=nums[4]=2
                    //此时满足条件  但是需要排除后面和nums[left]以及nums[right]相等的连续元素

                }
                else if(nums[left]+nums[right]<target)
                    left++;
                else if(nums[left]+nums[right]>target)
                    right--;
            }
        }
        return ans;
    }
}
//O(n^2)
//O(logn)  排序的空间复杂度
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
41
42
43
44
45
46
47

31. 下一个排列

https://leetcode-cn.com/problems/next-permutation/

思路： 想要获取下一个排列，要进行以下3步（以2 3 1 为例）

1. 从后往前寻找到a[i] 使得a[i]<a[i+1] 对应例子中a[i]=2 这样使得a[i+1]…a[n-1]都是非递增的
2. 在区间[i+1,n-1]内从后往前寻找第一个a[j],使得a[j]>a[i] 对应例子中a[j]=3
3. 交换a[i]和a[j] 由于a[i+1,n-1]本身就是非递增的了 交换之后该区间还是递减的
4. 翻转a[i+1,n-1]区间内的元素 这样就使得该区间内的元素由递减变成递增的， 相对序较小

ps: 特殊情况，当例子为3 2 1时，会发现第1步中找到的i=-1, 因此直接进行第4步，翻转[0,2]区间，即翻转所有元素，这与直接的观察结果也符合

class Solution {
    public void nextPermutation(int[] nums) {
        int n=nums.length;
        int i=n-2;
        while(i>=0&&nums[i]>=nums[i+1])//不能改成nums[i]>nums[i+1]
            i--;
        if(i>=0)
        {
            int j=0;
            for(j=n-1;j>=i+1;j--)
            {
                if(nums[j]>nums[i])
                    break;
            }
            swap(nums,i,j);
        }
        reverse(nums,i+1,n-1);
    }
    public void swap(int[] nums,int i,int j)
    {
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    public void reverse(int[] nums,int i,int j)
    {
        while(i<j)
        {
            swap(nums,i,j);
            i++;
            j--;
        }
    }
}
//O(n)
//O(1)
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

160. 相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

思路：先使用两个指针pA pB分别指向headA headB 当pA!=pB时 如果A链表没有遍历完，pA往后走一步，如果A遍历完了，就让pA指向headB, 从B链表的头部开始移动； 对于headB同理

392. 判断子序列

https://leetcode-cn.com/problems/is-subsequence/

思路：这里要求的是子序列，不是连续子序列，设置两个指针i,j分别扫描s和t, 具体做法为，当s[i]==t[j]时，i++, 而j一直往后走，如果最后i==s.length() 则匹配成功

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i=0,j=0;
        int m=s.length(),n=t.length();
        while(i<m&&j<n)
        {
            if(s.charAt(i)==t.charAt(j))
                i++;
            j++;
        }
        return i==m;
    }
}
//O(m+n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

进阶问题： 预处理出对于 t的每一个位置，从该位置开始往后每一个字符第一次出现的位置

构造一个dp数组dp[i][j]: 表示从t中的位置i开始字符第一次出现的位置
d p [ i ] [ j ] = { i , if  t [ i ] = = j d p [ i + 1 ] [ j ] , if  t [ i ] ! = j   dp[i][j] =

$$\begin{cases} i, & \text{if $t[i]==j$} \\ dp[i+1][j], & \text{if $t[i]!=j$ } \\ \end{cases}$$ dp[i][j]={i,dp[i+1][j],​if t[i]==jif t[i]!=j ​

如果在t中，i位置上面的字符就是j, 即t[i]==j 则dp[i][j]=j
如果不是， j 出现在位置 i+1 开始往后，即dp[i+1][j]

class Solution {
    public boolean isSubsequence(String s, String t) {
       
        int m=s.length(),n=t.length();
        int [][] dp=new int[n+1][26];//只有26个小写字母
        for(int i=0;i<26;i++)
            dp[n][i]=n;//t中的位置是[0,n-1] n位置额外腾出来表示不存在 
        //dp[i][j]=dp[i+1][j] 这样当t[n-1]!=j 时 dp[n-1][j]=dp[n][j]=n 表示n-1位置往后不存在字符j
        for(int i=n-1;i>=0;i--)//从后到前处理dp数组 因为当前位置的情况依赖于后面的
        {
            for(int c=0;c<26;c++)
            {
                if(t.charAt(i)==c+'a')
                    dp[i][c]=i;
                else
                    dp[i][c]=dp[i+1][c];
            }
        }
        int index=0;
        //s串是否是t串的子序列
        //m=s.length()  n=t.length()
        for(int i=0;i<m;i++)
        {
           
            int c=s.charAt(i)-'a';
            if(dp[index][c]==n)
                return false;//s中的字符c在t中不会出现 则可以判断不是子序列
            index=dp[index][c]+1;//c在t中出现的位置是dp[index][c]  所以s中的下一个字符和dp[index][c]比较
        }
        return true;

    }
}
//O(n*26+m)
//O(26*n)
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

26. 删除有序数组中的重复项

https://leetcode-cn.com/problems/remove-element/


思路：题目要求原地修改数值，最后返回的是数组的长度，可以使用两个指针，一个指针先固定在某个元素x，另外一个指针从元素x的下一个元素开始往后遍历，直到遇到一个元素y,y!=x, 然后将y放在x的下一个位置即可，重复这个过程，直到right指针遍历完数组

class Solution {
    public int removeDuplicates(int[] nums) {
        int left=0,right=1,n=nums.length;
        if(n==0)
            return 0;
        while(right<n){
           
            if(nums[right]!=nums[left])
            {
                nums[left+1]=nums[right];
                left++;   
            }
            right++;
        }
        return left+1;
    }
}
//O(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

27. 移除元素

思路：所以双指针，一个left指针指向当前构造出的新数组的最后一个元素，一个right指针往后寻找和val不等的元素，找到后就将该元素放置在left` 的位置上面

class Solution {
    public int removeElement(int[] nums, int val) {
        int left=0,right=0,n=nums.length;
        while(right<n){
            //right往后寻找和val不等的元素
            if(nums[right]!=val){
                nums[left]=nums[right];
                left++;
            }
            right++;
        }
        return left;//返回新数组的长度
        
    }
}
//o(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

83. 删除排序链表中的重复元素

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

思路：先使用一个指针left指向当前头节点，然后另外一个指针right往后寻找和left节点的值不一样的节点，找到后将right指向的节点连接在left节点后面，然后使left指向right, 继续上述过程； 最后left指向尾结点，需要断开left和后面重复节点的连接

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null)
            return null;
        ListNode left=head,right=head;
        while(right!=null){
            if(right.val!=left.val){//right指向的节点和left指向的节点值不同
                left.next=right;//right节点连接到left上
                left=right;//left更新为right
            }
            right=right.next;
        }
        left.next=null;//断开后面重复的连接
        return head;

    }
}
//O(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

283. 移动零

https://leetcode-cn.com/problems/move-zeroes/

思路：使用right和left两个指针，left指针指向已处理的左边的最后一个非0元素，right则往后寻找非0元素，当right找到了非0元素，分为2种情况：

1. left=right 说明此时right遇到的都是非0元素 不用处理
2. left!=right 则nums[left]=nums[right] nums[right]=0

class Solution {
    public void moveZeroes(int[] nums) {
        int n=nums.length;
        int left=0,right=0;
        while(right<n){
            if(nums[right]!=0)
            {
                if(right!=left){
                    nums[left]=nums[right];//把非0元素放到left位置上
                    nums[right]=0;//right位置上面放0
                }
                left++;//left=right&&nums[right]！=0 不用交换
            }
            right++;
        }
    }
}
//O(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

986. 区间列表的交集

https://leetcode-cn.com/problems/interval-list-intersections/


思路：对于两个区间，先获得两个区间左边界中的较大值，右边界中的较小值，如果这个较大值<=较小值，说明有交集，将该交集加入答案中，另外比较完当前区间后，需要移动右边界较小的区间，因为该区间不会和自己的区间列表内的元素有交集，也不会和另外一个区间列表的下一个区间有交集

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int n1=firstList.length,n2=secondList.length;
        ArrayList<int[]> ans=new ArrayList<>();
        if(n1==0||n2==0)
             return ans.toArray(new int[ans.size()][]);
        int i=0,j=0;
        while(i<n1&&j<n2){
            int start=Math.max(firstList[i][0],secondList[j][0]);
            int end=Math.min(firstList[i][1],secondList[j][1]);
            if(start<=end){
                ans.add(new int[]{start,end});
            }
            if(firstList[i][1]<secondList[j][1])//移动结束较早的区间
                i++;
            else
                j++;
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
//O(m+n)
//O(m+n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

870. 优势洗牌

https://leetcode-cn.com/problems/advantage-shuffle/

思路：类似于田忌赛马，将A中元素升序，B中元素降序，当A中的最大元素可以打败B中的最大元素时，则二者匹配；否则，用A中的最小元素来和B中的最大元素匹对

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->b[1]-a[1]);//降序 堆顶元素最大
        for(int i=0;i<nums2.length;i++){
            pq.offer(new int[]{i,nums2[i]});
        }
        Arrays.sort(nums1);//升序
        int[] ans=new int[nums1.length];
        int left=0,right=nums1.length-1;//left指向最小元素 right指向最大元素
        while(!pq.isEmpty()){
            int[] tmp=pq.poll();
            int index=tmp[0],maxVal=tmp[1];
            if(nums1[right]>maxVal){//A中最大>B中最大
                ans[index]=nums1[right];
                right--;
            }else{
                ans[index]=nums1[left];//A中目前最小-B中目前最大
                left++;
            }
        }
        return ans;
    }
}
//O(nlogn)
//O(n)
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

18. 四数之和

https://leetcode-cn.com/problems/4sum/

思路：类似于15. 三数之和，先对数组进行排序，方便去重，一段连续相同的数字只取第一个，然后先固定住第一个数字和第二个数字，对于第3个数字和第4个数字可以使用双指针的方法求解，在求解第3个数字和第4个数字的时候也需要去重

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans=new ArrayList<>();
        int n=nums.length;
        for(int a=0;a<n-3;a++){
            while(a>0&&a<n-3&&nums[a-1]==nums[a])//去重
                a++;
            for(int b=a+1;b<n-2;b++){
                while(b>a+1&&b<n-2&&nums[b-1]==nums[b])//去重
                    b++;
                int left=b+1,right=n-1;
                int val=target-nums[a]-nums[b];
                while(left<right){
                    if(nums[left]+nums[right]==val){//找到1个答案
                        List<Integer> tmp=new ArrayList<>();
                        tmp.add(nums[a]);
                        tmp.add(nums[b]);
                        tmp.add(nums[left]);
                        tmp.add(nums[right]);
                        ans.add(tmp);
                        left++;
                        right--;
                        while(left<right&&nums[left]==nums[left-1])//去重
                            left++;
                        while(left<right&&nums[right]==nums[right+1])//去重
                            right--;
                    }
                    else if(nums[left]+nums[right]<val)//和偏小 left++
                        left++;
                    else if(nums[left]+nums[right]>val)//和偏大 right--
                        right--;
                }
            }
               
        }
        return ans;


    }
}
//O(n^3)
//O(nlogn)
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
41
42
43

821. 字符的最短距离

https://leetcode-cn.com/problems/shortest-distance-to-a-character/

思路：两遍扫描，第一遍求出每个字符距离左边最近的c的距离，第二次扫描遍历每个字符距离右边最近的c的距离，取二者中的较小值即可

class Solution {
    public int[] shortestToChar(String s, char c) {
        int n=s.length();
        int[] ans=new int[n];
        Arrays.fill(ans,n+2);
        int j=-1;
        for(int i=0;i<n;i++){
            if(s.charAt(i)==c)
                j=i;
            if(j!=-1)
                ans[i]=Math.min(ans[i],i-j);
        }
        j=-1;
        for(int i=n-1;i>=0;i--){
            if(s.charAt(i)==c)
                j=i;
            if(j!=-1)
                ans[i]=Math.min(ans[i],j-i);
        }
        return ans;
    }
}
//O(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24