算法刷题笔记 Day_2 7道数组题

淩亂°似流年 2024-03-26 16:06 78阅读 0赞

## 数组题目——双指针技巧秒杀7道数组题目 ##

**目录**

数组题目——双指针技巧秒杀7道数组题目

1.快慢指针技巧

2.左右指针的常用算法

--------------------

#### 1.快慢指针技巧 ####

① 力扣第 26 题「 [删除有序数组中的重复项][Link 1]」——Easy，让你在有序数组去重：

class Solution {
        public int removeDuplicates(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
            int slow = 0, fast = 0;
            while (fast < nums.length) {
                if (nums[fast] != nums[slow]) {
                    slow++;
                    // 维护 nums[0..slow] 无重复
                    nums[slow] = nums[fast];
                }
                fast++;
            }
            // 数组长度为索引 + 1
            return slow + 1;
        }
    }

拓展：

② 力扣第 83 题「 [删除排序链表中的重复元素][Link 2]」——Easy，如果给你一个有序的单链表，如何去重呢？

这个的原理和上面这道题是一样的原理，都是双指针来操作的！只不过是链表版本的.

class Solution {
        public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode slow = head,fast = head;
        while (fast!=null){
            if (slow.val != fast.val){
                slow = slow.next;
                slow.val = fast.val;
            }
            fast = fast.next;
        }
        //关键的一步 slow断开后续的无用数值
            slow.next = null;
        return head;
        }
    }

**除了让你在有序数组/链表中去重，题目还可能让你对数组中的某些元素进行「原地删除」**。

③ 比如力扣第 27 题「 [移除元素][Link 3]」——Easy，下面是解法：

该题的解法 同样和上面两题的解法相同！

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

注意这里和有序数组去重的解法有一个细节差异，我们这里是**先**给 `nums[slow]` 赋值然后再给 `slow++`，这样可以**保证** `nums[0..slow-1]` 是不包含值为 `val` 的元素的，最后的结果数组长度就是 `slow`。

④ 接下来看看力扣第 283 题「 [移动零][Link 4]」——Easy：

给你输入一个数组 `nums`，请你**原地修改**，将数组中的所有值为 0 的元素移到数组末尾。

class Solution {
        public void moveZeroes(int[] nums) {
        int slowFlag = removeElement(nums,0);
        for (;slowFlag<nums.length;slowFlag++){
            nums[slowFlag] = 0;//将数组后面的置零！
            }
        }
        int removeElement(int[] nums,int val){
            int slow=0,fast=0;
            while (fast<nums.length){
                if (nums[fast] != val){
                    nums[slow] = nums[fast];
                    slow++;
                }
                fast++;
            }
            return slow;
        }
    }

这题的解法，还是上面双指针先排除指定元素（0），然后在后续添加上0。即可解决！

⑤ 数组中另一大类快慢指针的题目就是「**滑动窗口算法**」，这个放到后面单独学习。原理当然也是快慢指针来解决的！

#### 2.左右指针的常用算法 ####

① **二分查找**

int binarySearch(int[] nums, int target) {
        // 一左一右两个指针相向而行
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = (right + left) / 2;
            if(nums[mid] == target)
                return mid; 
            else if (nums[mid] < target)
                left = mid + 1; 
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }

② **两数之和**

力扣第 167 题「 [两数之和 II][II]」——Medium：

class Solution {
        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){
                return new int[]{left + 1,right + 1};
            } else if (sum > target) {
                right--;
            }
            else if (sum < target) {
                left++;
            }
        }
        return new int[]{-1,-1};
        }
    }

这题的主要思路就是，通过左右指针，对比sum和target哪个大，然后把左右指针对应的位置变化就可以了！最后需要注意的点是返回的数组长度是需要+1的。

③ **反转数组**

扣第 344 题「 [反转字符串][Link 5]」——Easy，让你反转一个 `char[]` 类型的字符数组，我们直接看代码：

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

**关键点**：不要给另外的数组分配额外的空间，你必须**[原地][Link 6]修改输入数组**、使用 O(1) 的额外空间解决这一问题。我们解决的办法，任然是通过**左右指针**来解决！

④ **回文串判断**

力扣第 5 题「 [最长回文子串][Link 7]」——Medium：

class Solution {
        public String longestPalindrome(String s) {
        String res = "";
            for (int i = 0; i < s.length(); i++) {
                String s1 = palindrome(s, i, i);
                String s2 = palindrome(s, i, i + 1);
                // res = longest(res, s1, s2)
                res = res.length() >= s1.length() ? res : s1;
                res = res.length() >= s2.length() ? res : s2;
    //            System.out.println("res--"+res+"   "+res.length());
            }
            return res;
        }
    
        //返回查找的回文串
        String palindrome(String s, int l, int r) {
            // 防止索引越界
            while (l >= 0 && r < s.length()
                    && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;  //指针左右移动 扩展区域！
            }
            return s.substring(l+1, r);
        }
    }

提升：**charAt()** 方法用于返回指定索引处的字符。索引范围为从 0 到 length() - 1。

在上述题解当中，首先是通过palindrome（）来查找到合适的回文串，然后在上面的for循环中，依次查找（**奇数**字符串和**偶数**字符串都能兼顾），判断，使用？：，；三点式来判断，找到最长的回文字符串。需要关注的是下面这个式子。

**res = res.length() >= s1.length() ? res : s1;**

**参考资料**：[双指针技巧秒杀七道数组题目 :: labuladong的算法小抄][_ labuladong]

[Link 1]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[Link 2]: https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
[Link 3]: https://leetcode.cn/problems/remove-element/
[Link 4]: https://leetcode.cn/problems/move-zeroes/
[II]: https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
[Link 5]: https://leetcode.cn/problems/reverse-string/
[Link 6]: https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[Link 7]: https://leetcode.cn/problems/longest-palindromic-substring/
[_ labuladong]: https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/shuang-zhi-fa4bd/