Codetop几道高频面试题

CodeTop几道高频面试题

最近完成代码随想录的一刷，想看看具体在企业面试的过程中会有什么高频的手撕题，于是去了Codetop进行查找，还有不少。这里简单地准备了几道题目进行归纳总结，后续理解了再过来补充~

​

一、03. 无重复字符的最长子串

1.1 题目说明

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

示例 1:

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

示例 2:

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

提示：

• 0 <= s.length <= 5 * 104

• s 由英文字母、数字、符号和空格组成

  ​

1.2 解答分析

• 找到不含有重复字符的最长子串的长度，其实本质上就是记录两端点的位置值，判断形成的窗口内部不存在重复的字符即可。

• 方法1：最直接的想法是：滑动窗口+哈希表去重

  • 滑动窗口给出两个指针的边界值，固定好左指针，右指针移动的时候对hashmap记录过的进行判断，遇到重复的直接左指针进行覆盖下一位。例如："aab",在第一个a后再遇到a，左指针指向第二个。

  • 如果没有，就读入hashmap

  • 最后返回的是窗口的长度最大值，注意最后得+1，算上边界值。

    ​

• 方法2数组记录，替换掉hashmap,双指针滑动窗口

  • 创建长度为全部的128位字符的数组，用来统计ASCII码范围内的字符出现次数。

  • 注意：char c = arr[right]; 将字符串中的字符取出并赋值给 c，而 c 的值实际上是字符的 Unicode 编码。然后，可以使用 c 作为数组 pos 的下标进行访问和操作。当程序执行到 pos[c]++; 时，实际上是将字符 c 的ASCII码值作为数组下标，然后将对应位置的计数加一。

    ​

1.3 具体代码

• 方法1：

  class Solution{
      public intlngthOfLongestSubstring(String s){
          //利用滑动窗口
          int left=0;
          int res=0;
          HashMap<Character,Integer> map=new HashMap<>();
          //特例的判断
          if(s.length()==0){
              return 0;
          }
          for(int right=0;right<s.length();right++){
              if(map.containsKey(s.charAt(right))){
                  left=Math.max(left,map.get(s.charAt())+1);
              }
              map.put(s.charAt(right),right);
              res=Mth.max(res,right-left+1);
          }
          return res;
      }
  }
  
  /**
  或者是直接将S 字符串转化为字符串数组,char []s1=s.toCharArray();
  */

  • 复杂度分析：

  • 时间复杂度：$O(n)$

    遍历字符串：时间复杂度为O(n)。

    1. 在哈希表中查找键值对或插入键值对：平均时间复杂度为 O(1)，最坏情况下（哈希冲突）为 O(n)。
    2. 取两个数的最大值：时间复杂度为 O(1)。

    因此，总的时间复杂度为 O(n)。

  • 空间复杂度：$O(n)$ ,利用了HashMap

    ​

• 方法2：

  class Solution {
      public int lengthOfLongestSubstring(String s) {
          char arr[]=s.toCharArray();
          int pos[]=new int[128];//将全部的字符进行排列组合
         int ans=0,left=0;//规定最后的答案以及对应的指针变量
         for(int right=0;right<arr.length;right++){//右指针
             char c=arr[right];
             pos[c]++;
             while(pos[c]>1){
                 pos[arr[left]]--;//含有重复的字符
                 left++;//左指针右移
             }
             ans=Math.max(ans,right-left+1);//返回字符串的长度
         }
         return ans;
      }
  }
  //注意这里：将字符串中的字符取出并赋值给 c，而 c 的值实际上是字符的 Unicode 编码，这也是我们将数组的大小定义为128的原因。

  • 复杂度分析：

    • 时间复杂度：$O(n)$，同上方法分析

    • 空间复杂度： $O(1)$，常规数组。

      ​

二、92. 反转链表 II

2.1 题目分析

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表

示例1：

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

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

​

提示：

• 链表中节点数目为 n

• 1 <= n <= 500

• -500 <= Node.val <= 500

• 1 <= left <= right <= n

  ​

2.2 利用递归法进行解答

• 这里我们详细说明对于完整链表反转递归法的步骤过程：

  1. 输入一个头节点head，此时要求的是按照head为头节点的的时候的链表进行反转，并且返回反转之后的头结点

  2. 此时如果输入ListNode last=reverse(head.next);会执行下图的历程：

     

  3. 得到的结果是：

     

  4. 根据此时的函数定义，reverse函数会返回反转之后的头节点，这里我们利用last进行接收。

  5. 再输入head.next.next=head;

     

  6. 最后输入：head.next=null;return last;

     

  7. 注意base case的结束条件：if (head.next == null) return head;

  8. 当链表递归反转之后，新的头结点是 last，而之前的 head 变成了最后一个节点，别忘了链表的末尾要指向 null：head.next=null;

     ​

• 如果是反转链表的前N个节点

  1. 函数定义如下：

     // 将链表的前 n 个节点反转（n <= 链表长度）
     ListNode reverseN(ListNode head, int n)

     ​

  2. 对于这样的链表，执行的是reverseN(head,3):

     

  3. 给出相关的代码：

     ListNode successor = null; // 后驱节点
     
     // 反转以 head 为起点的 n 个节点，返回新的头结点
     ListNode reverseN(ListNode head, int n) {
         if (n == 1) { 
             // 记录第 n + 1 个节点
             successor = head.next;
             return head;
         }
         // 以 head.next 为起点，需要反转前 n - 1 个节点
         ListNode last = reverseN(head.next, n - 1);
     
         head.next.next = head;
         // 让反转之后的 head 节点和后面的节点连起来
         head.next = successor;
         return last;
     }   

     

  4. base case变为n==1，反转一个元素，就是他本身，记录后驱节点；注意最后需要加上后驱节点successor（第n+1个节点），在反转之后将head进行连接。

     ​

• 那对于本题来说，其实就是找到区间left和right的取值，当此时的left==1的时候，实际上和之前的反转前N个节点是一样的思路，如果不一样，那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……；可以得出最后的代码答案。

  ​

2.3 递归法具体代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution{
    ListNode successor=null;
    public ListNode reverseN(ListNode head,int m){
        if(m==1){
            successor=head.next;
            return head;
        }
        ListNode last=reverseN(head.next,m-1);
        head.next.next=head;
        head.next=successor;
        return last;
    }
    
    public ListNode reverseBetween(int head,inr left,int right){
        if(left==1){
            return reversN(head,right);
        }
        head.next=reverseBetween(head.next,left-1,right-1);
        return head;
    }
}

• 复杂度分析：

  • 时间复杂度：$O(m + right)$

    • 在 reverseN 方法中，通过递归反转链表的前 m 个节点。递归的深度最多为 m，所以该方法的时间复杂度为 O(m)。
    • 在 reverseBetween 方法中，递归调用 reverseBetween，直到找到需要反转的起始位置。递归的深度最多为 left，所以该方法的时间复杂度为 O(left)。
    • 在 reverseBetween 方法中，将指定区间的节点进行反转操作，包括修改节点的指针指向。这部分操作的时间复杂度为 O(right - left)。

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

    • 在 reverseN 方法中，使用了一个全局变量 successor 来存储当前节点的后继节点。因为只有一个 successor 变量，所以该方法的空间复杂度为 O(1
    • 在 reverseBetween 方法中，递归调用 reverseBetween，每次都会创建新的函数调用栈，但是除了递归调用之外没有使用额外的空间，所以该方法的空间复杂度为 O(1)。

    ​

2.4 给出完整实现代码

• ListNode和具体的实现类

import java.util.Scanner;

class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
        this.val=val;
        this.next=null;
    }
    ListNode(int val,ListNode next){
        this.val=val;
        this.next=next;
    }
}

public class test1 {
    static ListNode succe=null;

    /**
     * 创建链表
     */
    public static ListNode createLinkedList(int[] values){
        ListNode head=new ListNode(0); //创建头节点
        ListNode curr=head; //当前的指针

        for(int value:values){
            curr.next= new ListNode(value); //将当前的节点的next指针指向下一个新的节点
            curr=curr.next; //更新当前的节点指针
        }
        return head.next; //返回链表的真实起始节点
    }

    /**
     * 打印链表的输出
     */
    public static void print(ListNode head){
        ListNode list=head;
        while(list!=null){
            System.out.print(list.val+" ");
            list=list.next;
        }
        System.out.println();
    }

    /**
     * 递归反转整个链表
     */
    public static ListNode reverse(ListNode head){
        if(head ==null || head.next==null)  return head;
        ListNode last=reverse(head.next);
        head.next.next= head;
        head.next=null;
        return last;
    }

    /**
     * 反转链表的前
     */

    public static ListNode reverseN(ListNode head, int n) {

        if (n == 1) {
             // 记录第n+1个节点
            succe = head.next;
            return head;
        }

        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = succe;  // 反转之后，head节点和之前的节点连起来
        return last;
    }

    /**
     * 反转指定范围的链表
     * 递归法
     */
    public static ListNode reverseBetween(ListNode head,int m,int n){
       if(m==1){
           return reverseN(head,n);
       }
       // 前进到反转的起点的话，直接进行
        head.next=reverseBetween(head.next,m-1,n-1);
       return head;
    }


    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.print("请输入链表的长度值：");
        int n=in.nextInt();
        int[]values=new int[n];
        System.out.println("请依次输入链表的值：");
        for(int i=0;i<n;i++){
            values[i]=in.nextInt();
        }

        ListNode linked=createLinkedList(values);
        ListNode linked1=createLinkedList(values);
        ListNode linked2 = createLinkedList(values);

        //遍历打印，尝试输出
        System.out.println("原始链表的值是：");
        print(linked);


        //全部反转原始的链表关系
        ListNode re=reverse(linked);
        System.out.println("全部反转链表是：");
        print(re);

        //实现反转前n个节点
        System.out.println("对原始的链表，请输入从前第几个节点开始反转：");
        int k=in.nextInt();
        ListNode reN=reverseN(linked1,k);
        System.out.println("前自定义个节点进行反转后得到的链表为：");
        print(reN);

        //反转指定范围的数据
        System.out.println("请依次输入反转的区间：");
        int a= in.nextInt();
        int b=in.nextInt();
        ListNode resB=reverseBetween(linked2,a,b);
        System.out.println("指定范围内的反转得到的链表：");
        print(resB);
    }
}

​

2.5 利用双指针迭代进行解答

• 还有一种做法是不利用递归的方式，直接利用指针和哨兵节点进行交换：哨兵节点解决的是当left==1的时候的p0的指向问题。

  class Solution{
      public ListNode reverseBetween(ListNode head,int left,int right){
          ListNode dummy=new ListNode(0,head); //哨兵节点，并将其 next 指向原始链表的头节点 head
          ListNode p0=dummy;
          for(int i=0;i<left-1;i++){
              p0=p0.next; //在left节点的上一个节点
          }
          ListNode pre=null;
          ListNode cur=p0.next;
          for(int i=0;i<right-left+1;i++){ //需要反转的节点个数
              ListNode nxt=cur.next;
              cur.next=pre;
              pre=cur;
              cur=nxt;
          }
          //循环结束的时候，pre指向的是反转区间的最后一个节点； cur 则指向了反转区间之后的第一个节点。
          p0.next.next=cur; //指向反转区间的原起始位置
          p0.next=pre; //指向反转区间的原前一个节点
          return dummy.next; //返回反转后的链表头节点
      }
  }
  

  • 最后两行为（注意图中并没有包含哨兵节点，如果有哨兵则是上述代码的写法）：

    p0.next=cur;
    p0=pre;

    

  • 复杂度分析：

    • 时间复杂度：$O(right-left)$

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

      ​

三、46. 全排列

3.1 题目说明

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 6

• -10 <= nums[i] <= 10

• nums 中的所有整数 互不相同

  ​

3.2 解答分析

A. 利用递归的思路直接进行排列

• 返回的是二维列表进行排列，具体的思路如下：

  1. 定义一个 permute 方法，它接收一个整数数组 nums 作为参数，并返回一个包含所有可能全排列的列表。
  2. 在 permute 方法内部，创建一个空列表 result 来存储最终的结果。
  3. 调用 backtrack 方法，传入 nums 数组、一个空列表作为当前生成的排列，以及 result 列表。
  4. 在 backtrack 方法中，首先判断当前生成的排列长度是否等于 nums 数组的长度。如果是，则将当前排列加入到 result 列表中。
  5. 否则，遍历 nums 数组，对于每个元素，检查是否已经在当前排列中。如果是，则跳过该元素。
  6. 如果不是，则将该元素添加到当前排列中，然后递归调用 backtrack 方法，继续生成下一个位置的元素。
  7. 在递归调用结束后，需要将当前添加的元素从当前排列中移除，以便进行下一轮的遍历。
  8. 最后，返回 result 列表作为最终的结果。

• 通过不断地递归调用 backtrack 方法，将所有可能的排列生成并存储在 result 列表中。这样就可以得到给定数组的所有可能全排列。

• 缺点比较明显：由于直接全排列循环递归，复杂度都是！级别的，对应的占用的空间也挺大的。

  ​

B. 利用回溯法

• 本质上还是递归法，但是可以套模板进行分析。利用深度优先搜索算法DFS即可进行操作。

  ​

3.3 具体代码

1. 递归法(包含测试代码用例main函数)

import java.util.ArrayList;
import java.util.List;

public class Permutations {
    //定义返回的二维列表
    public List<List<Integer>> permute(int[] nums){
        List<List<Integer>> result=new ArrayList<>();
        backtrack(nums,new ArrayList<>(),result);
        return result;
    }
    private void backtrack(int[] nums,List<Integer>temp,List<List<Integer>> result){
        if(temp.size()==nums.length){
            result.add(new ArrayList<>(temp));
        }else{
            for(int i=0;i<nums.length;i++){
                if(temp.contains(nums[i])){
                    //如果是已经遍历过了
                    continue;//跳过当前的判断的元素
                }
                temp.add(nums[i]);
                backtrack(nums,temp,result);
                temp.remove(temp.size()-1); //移动这个下标的元素
            }
        }
    }

    public static void main(String[] args) {
        Permutations permutations = new Permutations();
        int[] nums1={1,2,3};
        int[] nums2={1,2,3,4,0};
        int[] nums3={1,2,3,5};
        System.out.println(permutations.permute(nums1));
        System.out.println();
        System.out.println(permutations.permute(nums2));
        System.out.println();
        System.out.println(permutations.permute(nums3));

    }
}

• 复杂度分析：

  • 时间复杂度：O(n!)​

    • 在回溯算法中，每个位置都有 n 种选择，因此在最坏情况下，需要生成 n! 个排列。
    • 每个排列的生成需要遍历整个数组，所以总的时间复杂度为 O(n ~ n!)。

  • 空间复杂度：O(n)​

    • 递归调用 backtrack 方法时，会创建一个临时列表来存储当前的排列，而且递归调用会导致方法调用栈的增加。
    • 最坏情况下，递归调用 backtrack 方法的次数达到 n! 次，所以空间复杂度为 O(n!)。
    • 此外，在 permute 方法中还需要一个额外的列表 result 来存储所有排列，其大小也为 O(n!)。

    ​

2. 回溯法

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution{
    LinkedList<Integer> path=new LinkedList<>(); //存放符合条件的集合
    List<List<Integer>>result=new ArrayList<>(); //存放最后的结果集合
    boolean []used; //判断元素是否是遍历过的，设置标志
    public List<List<Integer>> permute(int[] nums){
        if(nums.length==0){
            return result;
        }
       used=new boolean[nums.length]; //数组元素对应的长度
       dfs(nums);
       return result;
    }
    public void dfs(int[] nums){
        if(path.size()== nums.length){
            result.add(new LinkedList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            //遍历过的元素
            if(used[i]){
                continue;
            }else{
                used[i]=true;
                path.add(nums[i]);
                dfs(nums);
                path.removeLast();
                used[i]=false;
            }
        }
    }
}

• 复杂度分析：（本质上和递归法相同）

  • 时间复杂度：O(n!)​

  • 空间复杂度：O(n!)​

    ​

四、215. 数组中的第K个最大元素

4.1 题目说明

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 105

• -104 <= nums[i] <= 104

  ​

4.2 解答分析

• 本题可以利用三种常见的方法进行解答：

  1. 调用API接口，对数组进行排序后进行选取对应位置的第k大的数组元素。时间复杂度直接为：$O(nlogn)$。
  2. 利用堆排序和优先序列进行排序，好处是比较通俗理解，但是时间复杂度分析比较繁琐。
  3. 利用快速排序，对当前的数组进行随机划分哨兵节点和三位置（大于、小于、等于）三部分，借助递归对每个部分进行排序即可。

• 面试中主推的是快速排序和递归的方法，当然也有优先队列和堆，不过那个可以直接调用接口，和最初的api有相似之处。下面给出快排的相关思路结构图：

• 

  ​

4.3 具体代码

1. 调用api

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //使用的是api进行 调用
        Arrays.sort(nums);
        return nums[nums.length-k];
   }
}

• 复杂度分析：

  • 时间复杂度: $O(NlogN)$ , 其中 NNN 为数组元素数量。

  • 空间复杂度: 取决于内置排序算法的具体设计。

    ​

2. 优先队列和堆

class Solution{
    public int findKthLargest(int[] nums,int k){
        //使用的是最小堆进行排序，自底向上依次减小
        //我们需要找到的就是最大的K个数中的最小的那个数，其中就是第K大的数
        //可以首先确定堆的高度为K，也就是收纳K个元素，接着读入的元素和堆顶的元素进行比较即可。大于就弹出
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for(int i=0;i<k;i++){
            queue.offer(nums[i]);
        }
        for(int i=k;i<nums.length;i++){
            int value=queue.peek();
            if(nums[i]>value){
                queue.poll(); //弹出
                queue.offer(nums[i]);
            }
        }
        return queue.peek(); //返回堆顶的元素
    }
}

• 复杂度分析：

  • 时间复杂度：$O(klogk + (n-k)logk)$

    假设输入数组的长度为 n。

    1. 初始化 PriorityQueue 的时间复杂度：O(klogk)，因为在循环中插入 k 个元素，每次插入的时间复杂度为 logk。
    2. 循环遍历剩余的元素：假设剩下的元素有 m 个，那么这部分的时间复杂度为 O((n-k)logk)，因为对于剩下的每个元素，最坏情况下需要进行 logk 次操作。

    因此，整体的时间复杂度为 O(klogk + (n-k)logk)。

  • 空间复杂度: $O(k)$

    空间复杂度则是 O(k)，因为最小堆中最多保存 k 个元素。

    ​

3. 快速排序

class Solution {
    public int quickSelect(List<Integer> nums, int k) {
        //使用的是快速选择进行排序的方法，其实就是简单的快速选择比较的区间，进行移动
        //随机选择基准数
        Random rand=new Random();
        int pivot=nums.get(rand.nextInt(nums.size()));

        //将大于、小于、等于pivot的部分元素进行划分为big\small\equal中
        List<Integer>big=new ArrayList<>();
        List<Integer>equal=new ArrayList<>();
        List<Integer>small=new ArrayList<>();

        for(int num:nums){
            if(num>pivot){
                big.add(num);
            }else if(num<pivot){
                small.add(num);
            }else{
                equal.add(num);
            }
        }

        //将第K大的元素放在big中去，递归进行划分
        if(k<=big.size()){
            return quickSelect(big,k);
        }

        //第k大元素在small中，递归进行划分的问题
        if(nums.size()-small.size()<k){
            return quickSelect(small,k-nums.size()+small.size());
        }

        // 第 k 大元素在 equal 中，直接返回 pivot
        return pivot;
   }
    public int findKthLargest(int[] nums, int k){
         List<Integer> numList=new ArrayList<>();
         for(int num:nums){
             numList.add(num);
         }
         return quickSelect(numList,k);
     }
}

• 注意：这段代码的含义是从一个名为 nums 的列表中随机选择一个元素作为 pivot。rand.nextInt(nums.size()) 会生成一个介于 0（包括）和 nums.size()（不包括）之间的随机整数，然后通过 nums.get() 方法获取该随机位置上的元素赋值给 pivot。

• 复杂度分析：

  • 时间复杂度：$O(n)$

    • 其中 N 为数组元素数量。
      对于长度为 N 的数组执行哨兵划分操作的时间复杂度为 O(N) 。

    • 每轮哨兵划分后，向下递归子数组的平均长度为 $\frac{N}{2}$。因此平均情况下，哨兵划分操作一共有 :$N + \frac{N}{2} + \frac{N}{4} + ... + \frac{N}{N} = \frac{N - \frac{1}{2}}{1 - \frac{1}{2}} = 2N - 1$

      （等比数列求和，复杂度为 $O(n)$。

  • 空间复杂度：$O(logn)$

    划分的函数的平均递归深度为$O(logN)$

    ​

五、15. 三数之和

5.1 题目说明

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

​

提示：

• 3 <= nums.length <= 3000

• -105 <= nums[i] <= 105

  ​

5.2 解答分析

• 重点要求是：排序、双指针、两次去重，也是解决本问题的三个关键点

1. 排序： 首先是对给定的整数数组nums进行排序。通过排序，可以使得相同的数字元素相邻，从而更加方便沟洫的去重操作和双指针查找。

2. 双指针：使用双指针left和right分别指向数组中的两端，然后在每一次循环中计算当前三个数组的和sum。再根据sum的值，通过不断移动left和right指针来逐步逼近满足条件的三元组，直到找到所有符合条件的三元组为止。

3. 两次去重：为了避免结果中出现重复的三元组，需要进行两次去重操作。

   • 第一次去重是在外层循环中，判断当前数字是否与前一个数字相同，如果相同则跳过，避免重复计算。

   • 第二次去重是在内层循环中，判断 left 和 right 指针所指的数字是否与前一个数字相同，如果相同则跳过，避免重复计算。

     ​

5.3 具体代码

class Solution{
    public List<List<Integer>> threeSum(int[] nums){
        // 定义3个指针，保证遍历数组中的每一个结果
        List<List<Integer>> res=new ArrayList<>();
        
        // 数组的长度
        int len=nums.length;
        
        // 当前数组的长度为空的话，或者是长度小于所求的长度3，直接退出即可
        if(nums==null || len<3){
            return res;
        }
        //1. 排序（对数组进行排序）
        Arrays.sort(nums); //快排
        
        //遍历数组的每一位元素
        for(int i=0;i<len-2;i++){
            // 由于已经是递增序列了
            // 如果此时遍历的元素大于0，则直接退出
            // 此时的数组为有序数组，最下的书都是大于0的话，那三个数之和一定也是大于0的
            if(nums[i]>0){
                break;
            }
            
            //3. 去重1
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            // 2. 双指针
            int left=i+1;
            int right=len-1;
            //当l不等于r的时候就继续遍历
            while(l<r){
                //将三数进行相加
                int sum=nums[i]+nums[left]+nums[right];
                //如果是0，将结果对应索引为止的值加入到结果集中去
                if(sum==0){
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    
                // 3. 去重2
                // 在左右指针移动的时候，对左右指针的值分别纪念性判断，如果存在重复，直接跳过
                // 去重，因为此时的i不变，当此时的l取到的数值和前一个数相同的话，不用计算，直接跳过
                   while(l<r && nums[l]==nums[l+1]){
                       l++;
                   }
                //同理，也对右指针去重
                    while(l<r && nums[r]==nums[r-1]){
                        r--;
                    }
                    // 将左右指针进行移动
                    l++;
                    r--;
                    
                }else if(sum<0){ //如果结果小于0，将左指针右移
                    l++;
                }else if(sum>0){ //如果结果大于0，将右指针左移
                    r--;
                }
            }
        }
        return res;
    }
}

• 复杂度分析：

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

  1. 最开始代码中对数组元素实现了排序，由于利用的是快速排序，此时的时间复杂度为：$O(nlogn)$
  2. 接着，代码实现了两层的嵌套循环，时间复杂度为：$O(n^2)$
     • 外层的循环遍历数组中的每一个元素，时间复杂度为：$O(n)$
     • 内层循环使用双指针技巧，由于左右指针由数组的两端向中间进行移动，时间复杂度也为$O(n)$
  3. 综上：时间复杂度为$O(n^2)$

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

  ​

六、141. 环形链表

6.1 题目说明

• 给你一个链表的头节点 head ，判断链表中是否有环。

  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

  如果链表中存在环 ，则返回 true 。 否则，返回 false

• 示例1：

  

  输入：head = [3,2,0,-4], pos = 1
  输出：true
  解释：链表中有一个环，其尾部连接到第二个节点。

  ​

6.2 解答方法

• 双指针，快慢指针问题；当slow和fast相遇的时候即可判断出该链表为环形链表。

• 扩展：

  1. 环形链表三连问：
     1. 是否有环 （上述快慢指针）
     2. 找出环的入口 （快慢指针重合的位置，此时再次重新遍历即可）
     3. 环中节点个数（快慢指针，从重合的节点开始计算）

• 为此，给出具体的代码：

  ​

6.3 具体代码

• 准备的环境函数：

  /**
   * 链表初始定义
   */
  class ListNode {
      int val;
      ListNode next;
  
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
   /**
       * 常规创建链表
       * @param nums
       * @return
       */
      public static ListNode createLinkedList(int[] nums) {
          ListNode dummy = new ListNode(0);
          ListNode curr = dummy;
          for (int num : nums) {
              curr.next = new ListNode(num);
              curr = curr.next;
          }
          return dummy.next;
      }
  
      /**
       * 创建带有环的链表
       * @param values
       * @param pos
       * @return
       */
      public static ListNode create(int[] values,int pos){
          ListNode head=createLinkedList(values); //创建头节点
          if(pos==0){
              return head;
          }
          ListNode curr=head; //当前的指针
          // 定位到第pos个节点
          int count=0;
  
          while (count < pos && curr.next != null) {
              curr = curr.next;
              count++;
          }
          // 记录第pos个节点的引用
          ListNode posNode = curr;
          // 遍历到链表尾部
          while (curr.next != null) {
              curr = curr.next;
          }
          // 将尾部节点的next指向第pos个节点
          curr.next = posNode;
  
          return head;
      }
  
      /**
       * 打印链表的输出
       */
  	public static void print(ListNode head,int n) {
          // 遍历输出环链表
          ListNode curr = head;
          int count = 0;
          System.out.println("经过环循环得到的链表为（2倍长度）：");
          while (count < n*2 && curr.next != null) {  // 控制输出次数，避免死循环
              System.out.print(curr.val+"->");
              curr = curr.next;
              count++;
          }
          System.out.print(curr.val);
      }
  

1. 判断是否有环

// 判断链表中是否存在环
    public static boolean hasCycle(ListNode head){
        if(head==null || head.next==null){
            return false;
        }
        ListNode slow=head;
        ListNode fast=head.next;
        while(slow!=fast){
            if(fast==null || fast.next==null){
                return false;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }

​

2. 输出环的入口

// 直接输出环的入口
    public static ListNode CycleOut(ListNode head){
        if (head == null || head.next == null) {
            return null; // 无环或者链表为空，返回null表示没有环
        }
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true; //存在环
                break;
            }
        }
        if (!hasCycle) {
            return null; // 无环，返回null表示没有环
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;

    }

​

3. 给出环中的元素个数(算上入口的节点)

public static int CycleNumber(ListNode head){
         if(head==null || head.next==null){
             return 0;
         }
         ListNode slow=head;
         ListNode fast=head.next;

         int count = 1; // 计数器初始值为1，因为fast已经指向了slow的下一个节点

         while(slow!=fast) {
             if (fast == null || fast.next == null) {
                 return 0;
             }
             slow = slow.next;
             fast = fast.next.next;
         }

         // 统计环中的节点个数
         fast=fast.next;  // fast向后移动一步，指向slow的下一个节点
         while(slow!=fast){
             fast=fast.next;
             count++;
         }
         return count;
    }

​

4. 辅助计算位置函数

// 辅助计算位置
    private static int getPosition(ListNode head, ListNode target) {
        int pos = 0;
        ListNode current = head;
        while (current != target) {
            current = current.next;
            pos++;
        }
        return pos;
    }

​

5. 自定义测试用例模块

public static void main(String[] args) {
        // 直接快慢指针进行查找
        Scanner in=new Scanner(System.in);
        System.out.print("请输入链表的长度: ");
        int n=in.nextInt();
        int []a=new int[n];

        // 输入到链表中的数据
        System.out.print("给出具体的数据: ");
        for(int i=0;i<n;i++){
            a[i]=in.nextInt();
        }
        // 创建并打印生成的含有环的链表
        // create()方法已经实现了

        //创建含有环的位置p
        System.out.print("请输入环pos的位置: ");
        int p=in.nextInt();
        ListNode v1=createNodeList.create(a,p);
        Print.print(v1,n);
        System.out.println();

    	
        // 可以朴素测试输入的链表关系：
        // 1 2 3 4 5 2
        // 创建新的链表关系
//        ListNode v2=new ListNode(1);
//        v2.next=new ListNode(2);
//        v2.next.next=new ListNode(3);
//        v2.next.next.next=new ListNode(4);
//        v2.next.next.next.next=new ListNode(5);
//        v2.next.next.next.next.next = v2.next;

        // 1. 测试是否含有环结构
        boolean test = hasCycle(v1);
        //打印
        System.out.println("是否含有环结构: "+test);

        // 2. 测试找到环的入口
        ListNode inn=CycleOut(v1);
//        System.out.println(inn.val);
        System.out.println("环中的入口元素位置为："+getPosition(v1,inn));
        System.out.println("环入口处的元素值为："+inn.val);

        // 3. 找到环中的元素个数
        int cnt=CycleNumber(v1);
        System.out.println("环中的元素个数有（算上入口的节点）："+cnt);
    }

​

• 输出测试样例截图：

  

  ​

七、5. 最长回文子串

7.1 题目说明

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000

• s 仅由数字和英文字母组成

  ​

7.2 解答分析

• 本题常见的就是两种方法：1. 中心扩展法；2. 动态规划

• 中心扩展法：

  • 从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。

    举个例子，str=acdbbdaastr = acdbbdaastr=acdbbdaa 我们需要寻找从第一个 b（位置为 333）出发最长回文串为多少。怎么寻找？

    首先往左寻找与当期位置相同的字符，直到遇到不相等为止。

    然后往右寻找与当期位置相同的字符，直到遇到不相等为止。

    最后左右双向扩散，直到左和右不相等。如下图所示：

    

    此时需要注意：每个位置向两边的扩展都会出现一个窗口的大小，我们需要不断更新maxLen的大小长度；

    因为最后返回的是具体的子串，所以最后调用方法sunstring(),需要记录maxLen的起始位置和最长的长度maxLen即可。

    ​

• 动态规划：

  • 我们其实也不用全部字符串都记录，比如用l和r形成窗口子串，用一个 boolean dp[l][r] 表示字符串从 i 到 j 这段是否为回文。试想如果 dp[l][r]=true，我们要判断 dp[l-1][r+1] 是否为回文。只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符。

  • 动态规划相当于是利用空间换时间，也就是将遍历过的元素储存起来，为后续的窗口内移动进行补充条件。

    ​

1. 确定dp数组以及下标的含义

   • 上述已经给出：boolean dp[l][r] 表示字符串从 i 到 j 这段是否为回文，l和r分别是左右移动的指针；

2. 确定初始方程

   • 若此时的l=r，说明此时即为字符本身，所以一定是回文串（字符）：dp[l][r]=true;

3. 状态转移方程

   • dp[l][r]=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true;

4. 确定遍历的顺序

   • 对于本题而言，我们需要知道的是最长回文子串，也就是按照。因此遍历的顺序是从左往右，从上到下，确定i的情况下，移动j，j在[0,i]中移动;

5. 举例推导验证

   • 其实不用验证了。字符串在(l-1)和（r+1)两个位置是否为相同的字符，当前子串的长度小于等于 2，则直接为回文子串；只有当子串的长度超过2，才是可以利用dp数组进行判断内部是否为回文子串;

     ​

7.3 具体代码

1. 中心扩散法

public String longestPalindrome1(String s) {

        if (s == null || s.length() == 0) {
            return "";
        }
        int strLen = s.length();
        int left = 0;
        int right = 0;
        int len = 1;
        int maxStart = 0;
        int maxLen = 0;

        for (int i = 0; i < strLen; i++) {
            left = i - 1;
            right = i + 1;
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                len++;
                left--;
            }
            while (right < strLen && s.charAt(right) == s.charAt(i)) {
                len++;
                right++;
            }
            while (left >= 0 && right < strLen && s.charAt(right) == s.charAt(left)) {
                len = len + 2;
                left--;
                right++;
            }
            if (len > maxLen) {
                maxLen = len;
                maxStart = left;
            }
            len = 1;
        }
        return s.substring(maxStart + 1, maxStart + maxLen + 1);

    }

• 复杂度分析：

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

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

    ​

2. 动态规划法

public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;

                    }
                }

            }

        }
        return s.substring(maxStart, maxEnd + 1);

    }

• 其中：对于代码if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {...}

  在代码中，s.charAt(l) 表示字符串 s 的第 l 个字符，s.charAt(r) 表示字符串 s 的第 r 个字符。

  代码中的条件 (r - l <= 2 || dp[l + 1][r - 1]) 是用来判断当前的子串是否为回文子串的关键条件。

  具体来说，如果 s.charAt(l) == s.charAt(r)，即当前子串的首尾字符相等，那么我们需要进一步判断子串 s[l + 1:r - 1] 是否为回文子串。

  我们有两种情况来判断：

  1. 当 r - l <= 2 时，意味着当前子串的长度小于等于 2。在这种情况下，无论该子串是否相等，它都是一个回文子串。因为长度为 0、1 或 2 的子串，只要字符相同，就一定是回文子串。

  2. 当 r - l > 2 时，即当前子串的长度大于 2。在这种情况下，我们需要根据之前计算得到的结果来判断子串是否为回文子串。如果 dp[l + 1][r - 1] 为 true，即子串 s[l + 1:r - 1] 是一个回文子串，那么当前子串 s[l:r] 也是回文子串。

  综上所述，如果满足条件 (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1]))，那么当前的子串 s[l:r] 就是一个回文子串。

  ​

• 复杂度分析：

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