数组相关算法以及双指针运用

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

1. 题目说明：原地只不能创建新数组再拷贝

2. 思路分析

   1. 使用快慢指针的技巧

      定义fast和slow，初始化为索引0。我们让fast走在slow前，每当nums[slow] != nums[fast]时，slow向前前进一步，并将nums[fast]赋值给nums[slow]

   2. 这样保证数组nums[0]到nums[slow]都是不重复的元素，返回slow + 1即为不重复元素数组的长度

   3. 示意图

3. 代码实现

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

4. LeetCode83 删除链表中的重复元素

1. 思路分析：与删除数组中的重复项一致，只不过快慢指针不再是索引，而是真正的指针

2. 注意事项：注意在fast遍历完链表后，要将slow.next = null，断开与后面重复元素的连接

3. 代码实现

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

4. LeetCode27 移除元素

1. 思路分析：和数组去重问题思路一致

   使用快慢指针，如果fast遇到值为val的元素，则直接跳过，否则就赋值给slow，slow向前一步

2. 注意事项：与去重问题的不同是

   这里是先给nums[slow]赋值，再让slow++，因此nums[0]到nums[slow-1]是不包含val的，返回的应该是slow

3. 代码实现

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

4. LeetCode283 移动零

1. 思路分析：可以将问题转化为移除元素0(即数组中移除元素0)，再将slow后面的元素都赋值为0

2. 代码实现

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

15. 后续出

16. LeetCode704 二分查找

    1. 思路分析：使用左右指针

       class Solution {
       public int search(int[] nums, int target) {
       int left = 0, right = nums.length - 1;
       while (left <= right) {
       int mid = (left + right) / 2;
       if (nums[mid] == target) {
       return mid;
       } else if (nums[mid] > target) {
       right = mid - 1;
       } else if (nums[mid] < target) {
       left = mid + 1;
       }
       }
       return -1;
       }
       }

17. LeetCode167 两数之和

    1. 思路分析：使用左右指针，左指针初始化为0(数组中最小的元素)，右指针初始化为numbers.length -1(数组中最大的元素)，定义一个sum = numbers[left] + numbers[right]，解法类似于二分查找，

       1. 如果sum == target，那么left，right即为所求
       2. 如果sum < target，那么因为right此时已经最大，只能将numbers[left]变大，即left++
       3. 如果sum > target，那么因为left此时已经最小，只能将numbers[right]变小，即right–

    2. 代码实现

       class Solution {
           public int[] twoSum(int[] numbers, int target) {
               if (numbers.length == 0) return new int[] {-1, -1};
               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};
           }
       }
       

18. LeetCode344 反转字符串 扩展为反转数组

1. 思路分析：使用左右指针，依次替换左右指针所指向的元素

2. 代码实现

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

19. LeetCode5 最长回文子串

1. 思路分析

   1. 使用左右指针，**从中心向两端扩散**
   2. 将回文串分为长度为奇数的回文串以及长度为偶数的回文串
      1. 长度为奇数的回文串，则输入的l = r
      2. 长度为偶数的回文串，则输入的r = l + 1
   3. 比较每次回文串的长度 //res = longest(res, s1, s2)

2. 代码实现

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