8. 双指针

8.1 1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //利用pair保存下标信息，first为元素值，second参数为原始下标
        pair<int,int> temp[nums.size()];
        for(int i=0;i<nums.size();i++){
            temp[i]={nums[i],i};
        }
        //排序，以便运用双指针
        sort(temp,temp+nums.size());
        int left=0,right=nums.size()-1;
        while(left<right){
            int sum=temp[left].first+temp[right].first;
            if(sum==target){
                return {temp[left].second,temp[right].second};
            }else if(sum>target){
                right--;  //让sum小一点
            }else if(sum<target){
                left++;  //让sum大一点
            }
        }
        return {-1,-1};
    }
};

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

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        int slow=0,fast=0;
        while(fast<nums.size()){
            if(nums[fast]!=nums[slow]){
                slow++;
                //记录不重复元素
                nums[slow]=nums[fast];
            }
            fast++;
        }
        //数组长度=索引+1
        return slow+1;
    }
};

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL){
            return NULL;
        }
        ListNode *slow=head,*fast=head;
        while(fast!=NULL){
            if(fast->val!=slow->val){
                // num[slow]=num[fast]
                slow->next=fast;
                //slow++
                slow=slow->next;
            }
            //fast++
            fast=fast->next;
        }
        //断开与后面重复元素的连接
        slow->next=NULL;
        return head;
    }
};

9.3 27. 移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow=0,fast=0;
        while(fast<nums.size()){
            if(nums[fast]!=val){
                //先赋值，再slow++，保证nums[0...slow-1]不包含val
                nums[slow]=nums[fast];                
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

9.4 283. 移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //先用双指针移除0，再在末尾补足0
        int slow=0,fast=0;
        while(fast<nums.size()){
            if(nums[fast]!=0){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        for(;slow<nums.size();slow++){
            nums[slow]=0;
        }
    }
};

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

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left=0,right=numbers.size()-1;
        while(left<right){
            int sum=numbers[left]+numbers[right];
            if(sum==target){
                return {left+1,right+1};
            }else if(sum>target){
                right--;
            }else if(sum<target){
                left++;
            }
        }
        return {-1,-1};
    }
};

9.6 5. 最长回文子串

class Solution {
public:
    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=s2;
            res=res.length()>s1.length()?res:s1;
            res=res.length()>s2.length()?res:s2;
        }
        return res;
    }
    //从中心向两端扩散，分奇数偶数讨论，回文串有可能是奇，有可能偶
    // 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
    // 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
    string palindrome(string s, int l, int r) {
        // 防止索引越界
        while (l >= 0 && r < s.length() && s[l]==s[r]) {
            // 双指针，向两边展开
            l--; r++;
        }
        // 返回以 s[l] 和 s[r] 为中心的最长回文串
        return s.substr(l + 1, r-1-l);
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.length();
        if(n<2) return s;
        int m_max=1;
        int start=0;
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i=0;i<n;i++){
            dp[i][i]=true;
        }
        for(int j=1;j<n;j++){
            for(int i=0;i<j;i++){
                if(s[i]!=s[j]){
                    dp[i][j]=false;
                }else{
                    if(j-i<3)
                        dp[i][j]=true;
                    else    
                        dp[i][j]=dp[i+1][j-1];
                }
                if(dp[i][j] && j-i+1>m_max){
                    m_max=j-i+1;
                    start=i;
                }
            }
        }
        return s.substr(start,m_max);       
    }
};