【LeetCode】双指针集锦

啊，要找工作了，耽误了好久的刷题重新捡起来。

不再按顺序刷题了（有时间也可以），主要按专题来刷，挑典型题。

L167：两数之和 II

这就是一个典型的双指针法。

原题链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

这道题比较典型的双指针，两个指针分别初始化在列表最前端和最末尾。

如果两个指针的和大于target，说明总和需要减小，后面那个指针向前。

如果两个指针的和小于target，说明总和需要增大，前面那个指针向后。

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        i, j = 0, len(numbers) - 1
        while i != j:
            if numbers[i] + numbers[j] == target:
                break
            elif numbers[i] + numbers[j] < target:
                i += 1
            elif numbers[i] + numbers[j] > target:
                j -= 1
        return [i+1, j+1]


if __name__ == '__main__':
    numbers = [2, 7, 11, 15]
    target = 9
    print(Solution().twoSum(numbers, target))

L633.平方数之和

原题链接：https://leetcode-cn.com/problems/sum-of-square-numbers/description/

这道题是平方数之和，时间复杂度比较低的办法依然是双指针法。

不过这里的判别条件需要做一个变动，因为这里是允许比如1（平方）+1=2的情况，也就是允许指针重叠，while条件需要做一定更改。

值得一提的是，这道题可以先对c取一个平方根，进一步的缩短时间复杂度。

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        import math
        max_idx = int(math.sqrt(c))
        i, j = 0, max_idx + 1
        while i <= j:
            res = i * i + j * j
            if res > c:
                j -= 1
            elif res < c:
                i += 1
            else:
                return True
        return False

L680.验证回文字符串 Ⅱ

原题链接：https://leetcode-cn.com/problems/valid-palindrome-ii/

这道题第一反应其实不是双指针哈哈哈哈，要我想我可能第一时间去dp方向想，但是刷的题是双指针的题，就会这么想。

这道题使用双指针来进行“删除”一个字符是比较好想的，但是问题在于怎么删。

我第一想法是使用一个标记位来允许指针“跳过”，也就是允许指针一次加/减2（正常是1）。但是这样会造成一个问题（这个问题不常见，直到458/460才出现），就是极端情况下，在当前并不知道需要删掉哪个。比如“cupuuffuupucu”，你不知道是第一个c删掉还是最后一个u删掉（它们都满足跳2步相同）。因此单纯的双指针跳转可能会产生问题。

因此采用另一种方法：使用双指针来判断——遇到了指针指向的值不相同时，把问题退化为回文串判断问题，分别删除两个指针指向的值，将剩余字符串直接进行字符串比较，从而判断是否为回文串。

由于省去了指针继续向内移动的时间，这种算法时间可以击败90%的用户（内存65%）。

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) < 2:
            return True
        left, right = 0, len(s) - 1
        while left <= right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            elif self.verify(s[left + 1: right+1]) or self.verify(s[left: right]):
                return True
            else:
                return False
        return True

    def verify(self, s):
        """
        直接判断是否为回文串
        :param s:
        :return:
        """
        if len(s) % 2 == 0:
            mid = int(len(s) / 2)
            if s[:mid] == s[mid:][::-1]:
                return True
            else:
                return False
        else:
            mid = len(s) // 2
            if s[:mid] == s[mid + 1:][::-1]:
                return True
            else:
                return False