力扣第3、215题

3.无重复字符的最长子串

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

思路：滑动窗口

  1. 定义一个map来存字符串的值和下标
  2. 用左右指针制造滑动窗口，右指针不断往右移，没有重复的字符就存到map，如果遇到重复的字符，就把左指针移到前面的重复字符的下一位（相当于把前面的重复字符删除）
  3. 移动指针过程中，记录窗口长度的最大值即为答案。
    1. var lengthOfLongestSubstring = function(s) {
    2.  let left = 0; //定义左指针
    3.  let maxLength = 0; //窗口最大长度
    4.  const map = new Map(); //map 存放字符串的值和下标
    5.  for(let right = 0; right < s.length; right++){
    6.        //如果出现了重复字符，则把指针移到重复字符的下一位
    7.        //因为每个字符都会存到map里，所以需要判断下标是否在左指针右边(就是滑动窗口里面)
    8.      if(map.has(s[right]) && map.get(s[right]) >= left){
    9.          left = map.get(s[right]) + 1;
    10.      }
    11.      map.set(s[right], right) //把字符存进map
    12.      maxLength = Math.max(maxLength, right-left + 1) //计算最大长度
    13.  }
    14.  return maxLength;
    15. };

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

    给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    image.png

    思路：考察排序，快排、堆排等

    快排方案：
    1. var findKthLargest = function(nums, k) {
    2.  const arr = quickSort(nums);
    3.  return arr[k-1];
    4. };
    5. let quickSort = (arr) => {
    6.  if(arr.length <= 1){return arr}
    7. let pivotIndex = Math.floor(arr.length / 2) 
    8. //向下取整找中间数为基准
    9. let pivot = arr.splice(pivotIndex,1)[0];
    10. //把基准单独抽出来
    11. let left = []
    12. let right = []
    13. for(let i = 0; i < arr.length; i++){
    14.  if(arr[i] > pivot){
    15.    left.push(arr[i])
    16.  }else{
    17.    right.push(arr[i])
    18.  }
    19. }
    20. return quickSort(left).concat([pivot],quickSort(right))
    21. //将左边的数组、基准、右边的数组拼起来
    22. }
    堆排方案