双指针技巧秒杀七道数组/链表题目

26. 删除有序数组中的重复项

83. 删除排序链表中的重复元素

27. 移除元素

283. 移动零

167. 两数之和 II - 输入有序数组

344. 反转字符串

5. 最长回文子串

删除有序数组中的重复项

双指针：

• slow：始终保持 [0...slow] 中无重复项
• fast：遍历数组

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;
    int fast = 0;
    while (fast < nums.length) {
        if (nums[slow] != nums[fast]) {
            slow++;
            nums[slow] = nums[fast];
        }
        fast++;
    }
    return slow + 1;
}

删除排序链表中的重复项

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null) {
        if (slow.val != fast.val) {
            slow.next = fast;
            slow = slow.next;
        }
        fast = fast.next;
    }
    slow.next = null;
    return head;
}

移除元素

双指针：

• slow：始终保持 [0...slow-1] 中没有需要被移除的元素
• fast：遍历数组

public int removeElement(int[] nums, int val) {
    if (nums.length == 0) return 0;
    int slow = 0;
    int fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

移动零

和「移除元素」几乎一样

public void moveZeroes(int[] nums) {
    if (nums.length == 0) return ;
    int slow = 0;
    int fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != 0) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    for (; slow < nums.length; slow++) nums[slow] = 0;
}

两数之和 II - 输入有序数组

利用左右指针不断的收缩区间

从两边到中心

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

反转字符串

利用左右指针交换元素

从两边到中心

public void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char t = s[left];
        s[left] = s[right];
        s[right] = t;
        left++;
        right--;
    }
}

最长回文子串

更多关于「回文子串」的整理可见 关于回文子串的两种方法：「中心扩展」&「动态规划」

利用左右指针扩张区间

从中心到两边

public String longestPalindrome(String s) {
    int[] ans = new int[]{0, 0};
    for (int i = 0; i < s.length(); i++) {
        int[] sub1 = isPalindromic(s, i, i);
        int[] sub2 = isPalindromic(s, i, i + 1);
        if (sub1[1] - sub1[0] > ans[1] - ans[0]) ans = sub1;
        if (sub2[1] - sub2[0] > ans[1] - ans[0]) ans = sub2;
    }
    return s.substring(ans[0], ans[1] + 1);
}
private int[] isPalindromic(String s, int i, int j) {
    while (i >= 0 && j < s.length()) {
        if (s.charAt(i) != s.charAt(j)) break;
        i--; j++;
    }
    return new int[]{i + 1, j - 1};
}