hot150-02-双指针

holic-x...大约 10 分钟

难度说明：🟢简单🟡中等🔴困难

hot150-02-双指针

🟢01-验证回文串（125）

1.题目内容

2.题解思路

思路：
- 【1】对字符串进行处理，只保留字母和数字，并全部转为小写
  - 技巧：s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase(); // 移出所有的非字母数字字符，并且将字母转换为小写
- 【2】对处理后的新字符串进行回文判断（反转法、工具法、双指针、栈等）

👻方法1：

/**
 * 125 验证回文串
 */
public class Solution2 {
    /**
     * 需要先对字符串进行处理，最终只保留字母内容并转化为小写，随后判断回文
     */
    public boolean isPalindrome(String s) {

        // 接收处理后的字符串
        StringBuffer str = new StringBuffer();

        // 处理字符串，只保留字母并转化为小写
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(Character.isLetterOrDigit(ch)) { // 'A' <= ch && ch <= 'Z' || 'a' <= ch && ch <= 'z' 此处设定是字母或数字才能通过测试用例
                str.append(Character.toLowerCase(ch));
            }
        }

        // 对处理后字符串大小进行判断
        if(str.length()<=1){
            return true;
        }

        // 通过双指针判断回文
        int left = 0;
        int right = str.length() - 1;
        while(left < right) {
            // 判断左侧和右侧字母是否一致，直到左右指针相遇结束
            if(str.charAt(left) != str.charAt(right)) {
                return false;
            }
            // 如果一致则继续判断（指针相互靠拢）
            left++;
            right--;
        }

        return true;
    }

}

复杂度分析
- 时间复杂度：
- 空间复杂度：

🟢01-判断子序列（392）

1.题目内容

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

2.题解思路

👻方法1：双指针法

思路：
- 【1】定义两个指针sp、tp，分别记录当前s、t比较的位置
- 【2】以t（源序列）为参照物进行遍历
  - 如果当前sp、tp指向的字符一致，则两个指针向前移动
  - 如果当前sp、tp指向的字符不一致，则tp指针向前移动，继续寻找下一个和sp指向字符一致的位置
  - 直到t字符串所有元素遍历完成，在这个过程中需要注意可能sp提前遍历结束（说明s就是t的子序列）
- 【3】最终结果返回：判断sp指针是否指向s的尾部，以此进行判定。如果不是指向尾部，则说明t遍历完了，s还有元素没有在t中匹配到

/**
 * 判断子序列（392）
 */
public class Solution1 {

    /**
     * 判断s是否为t的子序列：子序列在原字符串中可以不连续，但必须有序
     * s:target 要进行判断的子序列
     * t：source 源序列
     */
    public boolean isSubsequence(String s, String t) {

        // 定义两个指针记录当前遍历的位置
        int spoint = 0;
        int tpoint = 0;

        // 遍历s字符序列，依次校验是否匹配
        while(tpoint<t.length()){
            // 判断spoint是否提前结束
            if(spoint==s.length()){
                break;
            }
            // 校验当前两个指针指向的字符是否一致
            char curS = s.charAt(spoint);
            char curT = t.charAt(tpoint);
            if(curS==curT){
                // 如果匹配，两个指针都往前走，继续遍历下一个位置
                spoint++;
                tpoint++;
            }else{
                // 如果不匹配，则tpoint继续往前走
                tpoint ++;
            }
        }

        // 当t字符序列遍历完成，判断spoint是否走完
        return spoint==s.length();
    }
}

复杂度分析
- 时间复杂度：
- 空间复杂度：

// 简化版本
class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
}

🟡03-两数之和II-输入有序数组（167）

1.题目内容

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

2.题解思路

👻方法1：暴力法（超时，嵌套循环）

/**
 * 167 两数之和 II
 */
public class Solution1 {
    // 暴力法：双层循环
    public int[] twoSum(int[] numbers, int target) {
        // 嵌套循环遍历查找，元素不可重复使用
        for(int i = 0; i < numbers.length - 1; i++) {
            for(int j=i+1; j < numbers.length ; j++) {
                if(numbers[i] + numbers[j] == target) {
                    return new int[]{i+1,j+1}; // 坐标从1开始，因此此处返回的索引+1
                }
            }
        }
        return null;
    }
}

复杂度分析
- 时间复杂度：O(n²)
- 空间复杂度：O(1)

👻方法2：双指针

思路分析：数组本身有序，因此可以从两头进行找
- 定义左右指针，分别从数组两头开始出发
- 指针相遇意味循环查找操作结束，此处在查找过程中会去校验两个位置指向元素之和
  - sum==target：找到目标和，直接返回
  - sum>target：当前sum比较大，如果希望找到target，则需移动指针让sum变小（即右指针左移动）
  - sum<target：当前sum比较小，如果希望找到target，则需移动指针让sum变大（即左指针左移动）

/**
 * 167 两数之和 II
 */
public class Solution2 {

    /**
     * 双指针概念：数组本身有序，因此可以利用双指针分别从头、尾相向遍历，逐步靠拢，寻找target
     */
    public int[] twoSum(int[] numbers, int target) {
        // 定义双指针
        int left = 0, right = numbers.length - 1;

        // 指针相遇遍历结束
        while(left < right) {
            // 获取当前两个指针指向元素之和
            int sum = numbers[left] + numbers[right];
            if(sum==target){
                // 找到target，直接返回
                return new int[]{left+1, right+1}; // 数组从1开始，此处返回索引+1
            }else if(sum>target){
                // 如果sum比target大则说明要移动指针让sum变小
                right--;
            }else if(sum<target){
                // 如果sum比target小则说明要移动指针让sum变大
                left++;
            }
        }

        return new int[]{-1,-1};
    }
}

复杂度分析

时间复杂度：
空间复杂度：

🟡04-盛最多水的容器（11）

1.题目内容

2.题解思路

👻方法1：双指针

思路分析：area = min(h[left],h[right])*(right-left),因为right-left会随着指针移动变小，因此考虑怎样让min(h[left],h[right])尽量大 =>移动短边
- 【1】定义双指针，分别从数组两端开始移动
- 【2】移动过程中计算并更新maxArea的值，直到指针相遇遍历结束

/**
 * 11.盛水最多的容器
 */
public class Solution1 {
    /**
     * 双指针思路：
     * 盛水公式：area = min(h[left],h[right])*(right-left)
     * 因为right-left会随着指针移动变小，因此考虑怎样让min(h[left],h[right])尽量大
     * =>移动短边：移动短边或许可以拿到更大的值，因此采用这个思路切入
     */
    public int maxArea(int[] height) {
        // 定义响应结果
        int maxArea = Integer.MIN_VALUE;

        // 定义双指针
        int left = 0, right = height.length - 1;

        // 遍历数组，计算maxArea，指针相遇遍历结束
        while(left < right) {
            // 计算当前容器盛水，更新最大值
            int curArea = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, curArea);
            // 计算完成，指针继续移动（移动短边，以尽可能获取更大的值）
            if(height[left] < height[right]) {
                left++;
            }else if(height[left] >= height[right]) {
                right--;
            }
        }

        // 返回结果
        return maxArea;
    }

}

复杂度分析
- 时间复杂度：O（n）
- 空间复杂度：O（1）

🟡05-三数之和（15）

1.题目内容

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

2.题解思路

👻方法1：排序+双指针

思路分析：双指针思路
- 【1】对数组元素进行排序，以确保指针移动方向和思路是可行的
- 【2】循环遍历数组元素（[i,left,right]的顺序）
  - i从第一个元素位置开始
  - left：i+1（头部）
  - right：len-1（尾部）

/**
 * 15 三数之和
 */
public class Solution1 {

    /**
     * 双指针思路：
     * 理解出现三元组存在的情况：[0 0 0] [正 负相加]
     * 因此可以先对数组元素进行排序，然后循环遍历数组每个元素，并相应定义双指针来找这个三元组
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 定义结果集存储
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        // 对数组进行排序
        Arrays.sort(nums);

        // 循环遍历数组元素（从第1个元素开始，数组中的每个元素都可能称为三元组最左边那个数，例如[-1,0,1]）:[cur,left,right]
        for(int i=0;i<nums.length-2;i++) { // i 从第1个元素开始到倒数第二个元素结束
            // 定义双指针，进行遍历
            int left = i+1;
            int right = nums.length-1;
            while(left<right) {
                // 判断此时的三元组是否满足
                int sum = nums[i] + nums[left] + nums[right];
                if(sum==0) {
                    // res.add(Arrays.asList(nums[i], nums[left], nums[right])); 需进行去重
                    List<Integer> target = Arrays.asList(nums[i], nums[left], nums[right]);
                    if(!res.contains(target)) {
                        res.add(target);
                    }

                    // 找到满足的三元组，指针继续靠拢
                    left++;
                    right--;
                }else if(sum<0) {
                    // 如果sum比较小，则应该移动指针让sum变大
                    left++;
                }else if(sum>0){
                    // 如果sum比较大，则应该移动指针让sum变小
                    right--;
                }
            }
        }

        // 返回结果
        return res;

    }
}

复杂度分析
- 时间复杂度：
- 空间复杂度：

基于上述方式思路是正确的，但是直接提交会出现超时，主要还是要考虑对一些特殊或者重复的判断进行处理，来减少遍历次数

【1】排序后如果发现当前遍历元素大于0，则其后的组合不可能出现三元组，直接排除
【2】借助Set集合进行存储，自动去重

public class Solution2 {

    /**
     * 双指针思路：
     * 理解出现三元组存在的情况：[0 0 0] [正 负相加]
     * 因此可以先对数组元素进行排序，然后循环遍历数组每个元素，并相应定义双指针来找这个三元组
     * 进一步优化：将一些特殊的场景和重复的情况排除掉
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 定义结果集存储
        Set<List<Integer>> res = new HashSet<>();

        // 对数组进行排序
        Arrays.sort(nums);

        // 循环遍历数组元素（从第1个元素开始，数组中的每个元素都可能称为三元组最左边那个数，例如[-1,0,1]）:[cur,left,right]
        for(int i=0;i<nums.length-2;i++) { // i 从第1个元素开始到倒数第二个元素结束
            // 如果当前元素都大于0，那么其后面的元素肯定是比它大的，根本不可能构成三元组，直接跳出
            if(nums[i]>0) break;

            // 正常定情况下进一步判断，定义双指针，进行遍历
            int left = i+1, right = nums.length-1;
            while(left<right) {
                // 判断此时的三元组是否满足
                int sum = nums[i] + nums[left] + nums[right];
                if(sum==0) {
                    // 需进行去重(此处用set存储，自动去重)
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 找到满足的三元组，指针继续靠拢
                    left++;
                    right--;
                }else if(sum<0) {
                    // 如果sum比较小，则应该移动指针让sum变大
                    left++;
                }else if(sum>0){
                    // 如果sum比较大，则应该移动指针让sum变小
                    right--;
                }
            }
        }

        // 返回结果
        return new ArrayList<>(res);

    }
}

昵称

邮箱

网址

按正序
按倒序
按热度

hot150-02-双指针

预览: