数组算法题解决技巧

在排序数组中删除重复项目的快速指针技能

参考：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

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

扩展：删除链表中的重复元素

参考：https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

ListNode deleteDuplicates(ListNode head) {    if (head == null) return null;    ListNode slow = head, fast = head;    while (fast != null) {        if (fast.val != slow.val) {            // nums[slow] = nums[fast];            slow.next = fast;            // slow++;            slow = slow.next;        }        // fast++        fast = fast.next;    }    // 断开与后面重复元素的连接    slow.next = null;    return head;}

删除元素(原地删除数组中的元素)

参考：https://leetcode.cn/problems/remove-element/

/**     * 去除元素(原地删除元素)     * @param nums     * @param val     * @return     */    static int removeElement(int[] nums, int val){        if(nums.length == 0) return 0;        int slow = 0,fast = 0;        while (fast < nums.length){            if(nums[fast] != val){                nums[slow] = nums[fast];                slow++;            }            fast++;        }        return slow;    }

移动零(原地修改元素)

**参考：**https://leetcode.cn/problems/move-zeroes/

/**     * 去除元素(原地删除元素)     * @param nums     * @param val     * @return     */    static int removeElement(int[] nums, int val){        if(nums.length == 0) return 0;        int slow = 0,fast = 0;        while (fast < nums.length){            if(nums[fast] != val){                nums[slow] = nums[fast];                slow++;            }            fast++;        }        return slow;    }    /**     * 移动0(原地修改元素)     */    void moveZeroes(int[] nums){        int target = removeElement(nums, 0);        for (int i = target; i < nums.length; i++) {            nums[i] = 0;        }    }

左右指针技能二分搜索

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

两数之和

int[] twoSum(int[] nums, int target) {    // 左右两个指针相对行驶    int left = 0, right = nums.length - 1;    while (left < right) {        int sum = nums[left] + nums[right];        if (sum == target) {            // 主题要求的索引是从 1 开始的            return new int[]{left + 1, right + 1};        } else if (sum < target) {            left++; // 让 sum 大一点        } else if (sum > target) {            right--; // 让 sum 小一点        }    }    return new int[]{-1, -1};}

反转数组(反转字符串)

**参考：**https://leetcode.cn/problems/reverse-string/

/**     * 字符串反转     * @param s     */    void reverseString(char[] s) {        int left = 0,right = s.length-1;        while (left < right){            char temp = s[left];            s[left] = s[right];            s[right] = temp;            left++;            right--;        }    }

回文数判断(最长回文数)

boolean isPalindrome(String s) {    // 一左一右两指针相向而行    int left = 0, right = s.length() - 1;    while (left < right) {        if (s.charAt(left) != s.charAt(right)) {            return false;        }        left++;        right--;    }    return true;}

最长回文数

参考：https://leetcode.cn/problems/longest-palindromic-substring/

回文串的难点在于，回文串的长度可能是奇数或偶数，解决这个问题的核心是从中心扩散到两端的双指针技巧。

如果回文串的长度是奇数，则有一个中心字符；如果回文串的长度是偶数，则可以认为它有两个中心字符。因此，我们可以首先实现这样一个函数：

static 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);    }    static String longestPalindrome(String s) {        String res = "";        for (int i = 0; i < s.length(); i++) {            // 以 s[i] 为中心最长的回文子串            String s1 = palindrome(s, i, i);            // 以 s[i] 和 s[i+1] 为中心最长的回文子串            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 : s1;            res = res.length() > s2.length() ? res : s2;        }        return res;    }