力扣每日一题-双指针类型题目

167.两数之和（二）——输入有序数组

题目

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

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

示例:

输入: numbers = [2, 7, 11, 15], target = 9，输出: [1,2]。
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

题解

(1)双指针解法：初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

复杂度分析

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

空间复杂度：O(1)。

var twoSum = function(numbers, target) {
    let len = numbers.length
   
    if(!numbers||len<2){
        return 0
    }

    for(start=0,end=len-1;start<end;){
        if(numbers[start]+numbers[end]<target){
              start++
        }else if(numbers[start]+numbers[end]>target){
               end--
        }else{
            return [start+1,end+1]
        }
  
    }

};

(2)二分查找

在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。

复杂度分析

时间复杂度：O(nlog⁡n)，其中 n 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 O(n)，寻找第二个数使用二分查找，时间复杂度是 O(log⁡n)，因此总时间复杂度是 O(nlog⁡n)。

空间复杂度：O(1)

var twoSum = function(numbers, target) {
  let len = numbers.length,
    left = 0,
    right = len - 1,
    mid = 0
  for (let i = 0; i < len; ++i) {
    left = i + 1
    while (left <= right) {
      mid = parseInt((right - left) / 2) + left
      if (numbers[mid] == target - numbers[i]) {
        return [i + 1, mid + 1]
      } else if (numbers[mid] > target - numbers[i]) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
  }
  return [-1, -1]
}；

（3）使用map方法存储值，遍历数组中的每个元素，算出target与遍历元素的差，再去map中寻找是否有这么一个差。这样的话相当于空间复杂度变高了，是O(n)。

var twoSum = function(numbers, target) {
    let hashmap=new Map()
        for(let item in numbers){
        hashmap.set(numbers[item],item)
        }
        for(let i=0;i<numbers.length;i++){
        if(hashmap.has(target-numbers[i])){
        return [i+1,parseInt(hashmap.get(target-numbers[i]))+1]
        }
        }
return []
};

633.两数平方和

题目

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

示例 3：

输入：c = 4
输出：true

示例 4：

输入：c = 2
输出：true

示例 5：

输入：c = 1
输出：true

题解

(1)双指针解法（这里注意求某数的平方和时，可以直接从1到它的平方根遍历寻找）

var judgeSquareSum = function(c) {
    let i = 0
    let j = parseInt(Math.sqrt(c))
    while(i<=j){
        if(i**2+j**2>c){
            j--
        }else if(i**2+j**2<c){
            i++
        }else{
            return true
        }
    }
return false
}

因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。

(2)直接判断开方数

var judgeSquareSum = function (c) {
  if (c == 0) return true
  let big = Math.ceil(Math.sqrt(c)) //
  for (let i = 1; i <= big; i++) {
    // 原数减去当前数的平方再开方是否为整数
    if (Math.sqrt(c - i * i) % 1 == 0) {
      return true
    }
  }
  return false
};

时间复杂度为O(根号c) 空间复杂度为O(1)

(3)二分查找

var judgeSquareSum = function (c) {   
    let i = 0,j = parseInt(Math.sqrt(c))
    let low = i+1
    let mid = parseInt((low+j)/2)
    for(i;i<=j;i++){
        while(low<=j){
            if(Math.sqrt(c-i**2)<mid){
                j = mid-1  
            }else if(Math.sqrt(c-i**2)>mid){
                low = mid+1
            }else{
                return true
            }
        }
    }
return false
};

这种方法效果不是很好，但是在一定情况下也可以用。在力扣平台中显示超过限制。

345. 反转字符串中的元音字母

题目

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1：

输入：”hello”
输出：”holle”

示例 2：

输入：”leetcode”
输出：”leotcede”

提示：

元音字母不包含字母 "y" 。

题解

（1）还是使用双指针（这里注意还可以注意一下continue的用法）

var reverseVowels = function(s) {
  var l = 0, r = s.length - 1;
  s = s.split('')
  var yy = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'];
  while(l < r) {
    if(yy.indexOf(s[l]) === -1) {       //.indexof()用来检索包含某个子字符串的索引值   返回-1为没找到
      l++;
      continue;
    }
    if(yy.indexOf(s[r]) === -1) {
      r--;
      continue;                        //continue表示结束本次循环，但是不影响下次循环，break表示直接终止循环
    }
    [s[l], s[r]] = [s[r], s[l]];        //交换方法可以直接这么用
    l++;
    r--;
  }
  return s.join('');   //.join()方法表示使用引号内的数作为连接，将数组转化为字符串
};

另一种双指针方式：

var reverseVowels = function(s) {
   s = s.split('')
   let letter = 'aeiouAEIOU'
   let i = 0,j = s.length-1
   while(i<j){
       if(letter.indexOf(s[i])!==-1&&letter.indexOf(s[j])!==-1){
           [s[i],s[j]] = [s[j],s[i]]                       //交换的另一种简洁方式
           i++
           j--
          // swap(s,i++,j--)
       }
       if(letter.indexOf(s[i])==-1){
           i++
       }
       if(letter.indexOf(s[j])==-1){
           j--
       }
   }
   return s.join('')
};
// var swap = function(arr,a,b) {
//     const temp = arr[a]
//     arr[a] = arr[b]
//     arr[b] = temp
// }

（2）用set来判断是否存在元音字母，双指针查找，es6解构赋值交换(这个就是先遍历左边，如果一直没有，就一直遍历，有的话，则再遍历右边指针，如果正好也有，那么就交换，交换完了左边加；如果没有，则右边减。如果遍历的左边就没有的话，那么就左边加)，详情见代码。 这里也需要注意set的用法。

var reverseVowels = function(s) {
    let set = new Set(['a','e','i','o','u','A','E','I','O','U']);
    let arr = s.split('');
    let i =0;
    let j = arr.length-1;
    while(i<j){
        if(set.has(arr[i])){ // 左边是否有元音字母
            if(set.has(arr[j])){ // 如果左边有元音字母，右边也有，那么交换
                [arr[i],arr[j]] = [arr[j],arr[i]];
                i++;
            }
            j--;
        }else{
            i++;
        }
    }
    return arr.join('')
};

680.验证回文字符串||

题目

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: “aba”
输出: True

示例 2:

输入: “abca”
输出: True
解释: 你可以删除c字符。

注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

题解

（1）判断是否是回文串，用「双指针」的思路肯定没错：

设置头尾指针，如果指向的字符相同，则指针内移，继续检查。
如果指向的字符不同，还不能判死刑，看看能否通过删一个字符（要么删左指针指向的字符，要么删右指针指向的字符），使得剩下的字串是回文串

这里要写一个判断回文串的辅助函数，去判断「删去一个字符后」的子串，是否是回文串。

function isPali(str, l, r) { // 判断str是否回文
  while (l < r) {            
    if (str[l] != str[r]) {  // 指向的字符不一样，不是回文串
      return false;
    }
    l++;                     // 指针相互逼近
    r--;
  }
  return true;               // 始终没有不一样，返回true
}

var validPalindrome = function (s) {
  let l = 0, r = s.length - 1; // 头尾指针
  while (l < r) { 
    if (s[l] != s[r]) {      // 指向的字符不一样，还不能死刑 
      return isPali(s, l + 1, r) || isPali(s, l, r - 1); //转为判断删掉一个字符后，是否回文
    }
    l++;
    r--;
  }
  return true;
};

88.合并两个有序数组

题目

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[i] <= 109

题解

（1）从后往前——从尾部设置三个指针，向前遍历，这样就不需要额外使用空间了。（目前最好的方法）
1.用2个指针分别指向已有nums1和nums2的末尾，一个k指针指向nums1新的末尾。
2.进行2个指针数比较，哪个数大，就在nums1[k–]地方放置新的数
3.当nums2的数全部比较结束后终止循环。

var merge = function(nums1, m, nums2, n) {
    let k = m + n - 1, i = m - 1, j = n - 1;
    while(j >= 0){
        nums1[i] >= nums2[j] ?  nums1[k--] = nums1[i--] : nums1[k--] = nums2[j--]
    }
};

另一种（代码风格不一样）遍历完后

当 n > 0 时

• 说明 nums2 中还有剩余没有比较的数字
• 将其插入替换 nums1 数组前面n个数字即可

var merge = function(nums1, m, nums2, n) {
    let count = m + n;
    while(m > 0 && n > 0){
        nums1[--count] = nums1[m-1] < nums2[n-1] ? nums2[--n] : nums1[--m];
    }
    if(n > 0){
        nums1.splice(0,n,...nums2.slice(0,n));  //增加数组里的值
    }
};

• 时间复杂度 : O(n+m)。
• 空间复杂度 : O(1)。

（2）从前往后：一般而言，对于有序数组可以通过 双指针法 达到O(n+m)的时间复杂度。

最直接的算法实现是将指针p1 置为 nums1的开头， p2为 nums2的开头，在每一步将最小值放入输出数组中。

由于 nums1 是用于输出的数组，需要将nums1中的前m个元素放在其他地方，也就需要 O(m+n) 的空间复杂度。

var merge = function(nums1, m, nums2, n) {
    let left = 0;
    let right = 0;
    let tmp_nums1 = nums1.slice(0,m);
    let tmp_nums2 = nums2.slice(0,n);
    let result = [];
    while(left < m && right < n){
        if(tmp_nums1[left] < tmp_nums2[right]){
            result.push(tmp_nums1[left]);
            left++;
        }else{
            result.push(tmp_nums2[right]);
            right++;
        }
    }
    result = result.concat(tmp_nums1.slice(left)).concat(tmp_nums2.slice(right));//这里的目的就是把没有遍历的剩下的填补到后面
    for(let i = 0;i < result.length;i++){
        nums1[i] = result[i];
    }
};

141.环形列表

题目

给定一个链表，判断链表中是否有环。

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

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

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

题解

（1）快慢指针：定义快指针 fast , 慢指针 slow .

快指针每次走两格, 慢指针每次走一格.

若将两指针, 放在环中的任意位置 (环的节点数为 n ) .

在环中, 每次 fast 比 slow 多移动一格. 即在 fast 移动的方向上, fast 与 slow 之间的距离减一.
则至多 n 步后, fast 与 slow 相遇.

var hasCycle = function(head) {
    
    if(!head||!head.next){
        return false
    }
    let slow = head
    let fast = head   //等于head.next都可以
    while(fast!=null&&fast.next){
        slow = slow.next
        fast = fast.next.next
        if(slow == fast){
            return true
        }
    }
return false
};

时间复杂度: O(n), n 为链表 head 长度.

链表 head 中有环时.
在环中, 每次 fast 比 slow 多移动一格. 即在 fast 移动的方向上, fast 与 slow 之间的距离减一.
fast “追赶” slow 最长距离为 n ( 此时, head 为首尾相连的环形链表 ). 即, 最多 n 步后, fast 与 slow 相遇.

空间复杂度: O(1)

（2）标记(不是特别懂这个神奇的操作)

var hasCycle = function(head) {
    while (head && head.next) {
            if (head.flag) {
                return true
            } else {
                head.flag = 1;
                head = head.next;
            }
        }
    return false;

};

时间复杂度: O(n), n 为链表 head 长度.

空间复杂度: O(1)

524. 通过删除字母匹配到字典里最长单词

题目

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:

输入:
s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]

输出:
“apple”

示例 2:

输入:
s = “abpcplea”, d = [“a”,”b”,”c”]

输出:
“a”

题解

（1）使用双指针，在s与d[i]匹配的过程中，假设已匹配字母为count，d[i]的剩余未匹配长度为len，已有匹配最大值为maxL，如果len+count < maxL，那么就没有继续比较的必要，直接退出

如：s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]
1、s与匹配完apple后，maxL为5，
2、匹配abpcplea和monkey，monkey前两个字母不匹配，剩余字母只有“nkey”，已经不可能有更大的maxL，可以直接退出
2、匹配abpcplea和plea，plea的长度<maxL，也可以直接退出

(不是自己的想法，不是特别好理解，能看懂但是如果是自己做的话估计想不到这么复杂。)

var findLongestWord = function (s, d) {
  let maxL = 0
  let ind =  -1
  for (let i = 0; i < d.length; i++) {
    let now = find(s, d[i], maxL)  // 将d中每一个字符串与s进行对比
    // 1、如果d[i]的匹配字符个数与记录中的maxL相同，取字典序小的那个
    // 2、如果d[i]的匹配字符个数比记录中的maxL大，需要更新
    if ((maxL === now && d[i] < d[ind]) || maxL < now) {
      maxL = now
      ind = i
    }
  }
  function find(s, w, max) {
    let i = 0
    let j = 0
    let count = 0
    while (i < s.length && j < w.length && w.length - j + count >= max) {
      // 如果剩余长度+已匹配字符数>=max才有继续匹配的必要
      if (s[i] === w[j]) {
        j++
        count++
      }
      i++
    }
    if (count === w.length) {
      return count
    } else {
      return 0
    }
  }
  return d[ind] === undefined?'':d[ind]
};

（2）这题的关键就是怎么在字符串字典中找到那个对应的字符串。其实很简单。（目前js代码还没有写）
只要利用两个指针i,j，一个指向s字符串，一个指向sstr字符串，每一次查找过程中,i依次后移，若i,j对应的两个字符相等，则j后移，如果j可以移到sstr.length()，那么说明sstr中对应的字符s中都有，即s中删除一些字符后，可以得到sstr字符串，最后一步就是比较当前的结果字符与找到的sstr字符，按照题目的需求来决定是否改变结果字符，是不是还挺简单的呀。下面第一个是java版本，第二个是用js复现的（但是目前超出时间限制了）。

class Solution {
    public String findLongestWord(String s, List<String> d) {
        String str="";
        for(String sstr:d){
            for(int i=0,j=0;i<s.length()&&j<sstr.length();i++){
                if(s.charAt(i)==sstr.charAt(j)) j++;
                if(j==sstr.length()){
                    if(sstr.length()>str.length()||(sstr.length()==str.length()&&str.compareTo(sstr)>0))  str=sstr;
                }
            }
        }
        return str;
        
    }
}

var findLongestWord = function (s, d) {
  let str = ''
  let i = 0,j = 0,r = 0
  for(i,j;i<s.length,j<d.length;i++){
     while(r<d[j].length){
         if(s[i] === d[j][r]){
              r++
         }
         if(r === d[j].length){
            if(d[j].length()>str.length()||(d[j].length()==str.length()&&str>d[j]===true))  {
                str=d[j]
         }      
     } 
     }
     j++
  }
  return str
};