跳到主要内容

双指针

双指针通常从两端向中间靠拢，或者快慢指针同向移动，在有序数组或特定约束下能显著降低复杂度。

125. 验证回文串 (Valid Palindrome)​

题目描述​

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

解题思路​

使用双指针 i 和 j 分别指向字符串的头和尾。

  1. 跳过非字母数字字符。
  2. 比较 Character.toLowerCase(s.charAt(i)) 和 Character.toLowerCase(s.charAt(j))。
  3. 如果不相等则不是回文；否则 i++, j-- 继续。

Java 代码实现​

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < j && !Character.isLetterOrDigit(s.charAt(i))) i++;
            while (i < j && !Character.isLetterOrDigit(s.charAt(j))) j--;
            if (Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j--))) {
                return false;
            }
        }
        return true;
    }
}

392. 判断子序列 (Is Subsequence)​

题目描述​

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

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

解题思路​

双指针遍历。i 指向 s，j 指向 t。

  1. 如果 s.charAt(i) == t.charAt(j)，则 i++。
  2. 无论是否匹配，j++ 始终执行。
  3. 最后判断 i 是否等于 s.length()。

Java 代码实现​

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();
    }
}

167. 两数之和 II - 输入有序数组 (Two Sum II - Input Array Is Sorted)​

题目描述​

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序 排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。

如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

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

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

你所设计的解决方案必须只使用 O(1) 的额外空间。

解题思路​

头尾指针。

  1. i = 0, j = numbers.length - 1。
  2. 如果 sum == target 返回。
  3. 如果 sum < target，说明需要变大，i++。
  4. 如果 sum > target，说明需要变小，j--。

Java 代码实现​

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) return new int[]{i + 1, j + 1};
            if (sum < target) i++;
            else j--;
        }
        return new int[]{-1, -1};
    }
}

11. 盛最多水的容器 (Container With Most Water)​

题目描述​

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

解题思路​

贪心 + 双指针。

  1. 设置 i 和 j 指向两端。
  2. 容器高度由较低的一边决定：h = min(height[i], height[j])。
  3. 计算面积并更新最大值。
  4. 移动较小高度的一边，因为只有移动短板才可能让高度增加，进而弥补底变短带来的损失。

Java 代码实现​

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int max = 0;
        while (i < j) {
            max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) i++;
            else j--;
        }
        return max;
    }
}

15. 三数之和 (3Sum)​

题目描述​

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

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

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

解题思路​

排序 + 双指针。

  1. 排序数组。
  2. 遍历第一个数 nums[i]。如果 nums[i] > 0 后面不可能为 0，跳出。
  3. 判断去重：如果 i > 0 && nums[i] == nums[i-1] 跳过。
  4. 使用 left = i + 1, right = n - 1 寻找满足条件的 sum = 0。
  5. 找到解后，left 和 right 也要分别跳过重复项。

Java 代码实现​

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++; r--;
                } else if (sum < 0) l++;
                else r--;
            }
        }
        return res;
    }
}