「双指针技巧解决一些数组问题」

0 分类

双指针分类为快慢指针，左右指针。左右指针，两个指针相向/背而行；快慢指针则是同向而行，一快一慢。

单链表很多都是快慢指针，之前已经写出过。

这次来看看双指针解决数组问题，另一大类的滑动窗口下次再说。

1 快慢指针刷题

1.1 删除有序数组中的重复项

题解

因为要原地修改数组，所以不能使用new一个新数组的方法，所以直接双指针技巧，一个慢指针slow，一个快指针fast，fast相当于在前面探路，当找到一个不重复的元素就赋值给slow，并且让slow往前走一步，这样进行原地修改即可，最后返回个数，因为是0~slow都是不重复的，所以个数应该是slow+1。

Code

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[slow] != nums[fast])
            {
                ++slow;//移动到下一个坑位存储
                nums[slow] = nums[fast];
            }
            ++fast;
        }
        return slow + 1;//因为slow是从下标0开始的，所以要返回slow+1
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

结果

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

题解

其实将上述的方法拓展到链表中即可，还是快慢指针的技巧，一个快指针在前面探路，然后有不重复的直接把slow->next = fast即可。

Code

/**
 * 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) return head;
        ListNode *slow = head, *fast = head;
        while (fast != nullptr)
        {
            if (fast->val != slow->val)
            {
                slow->next = fast;
                slow = slow->next;
            }
            fast = fast->next;
        }
        slow->next = nullptr;//最后断开重复的
        return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

结果

1.3 移除元素

题解

与第一题删除重复元素差不多，还是快慢指针的思路。

Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //int size = nums.size();
        int slow = 0, fast = 0;
        while (fast < nums.size())
        {
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];//这样就使得从0~slow这个区间，nums是不包含val的
                slow++;
            }
            fast++;
        }
        return slow;//0~slow不包含val，此时返回slow就行，就是个数
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

所以归类出一个删除重复元素的模板：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //int size = nums.size();
        int slow = 0, fast = 0;
        while (fast < nums.size())
        {
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];//这样就使得从0~slow这个区间，nums是不包含val的
                slow++;
            }
            fast++;
        }
        return slow;//0~slow不包含val，此时返回slow就行，就是个数
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结果

1.4 移动0

题解

采用上述的删除模板，先把0全部删除，之后再进行末尾补0即可。

Code

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int p = removeElement(nums, 0);//去除0之后的数组长度
        for (; p < nums.size(); ++p)
        {
            nums[p] = 0;
        }
    }

    int removeElement(vector<int>& nums, int val)//
    {
        int fast = 0, slow = 0;
        while (fast < nums.size())
        {
            if (nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;//0~slow现在是不包含val的数
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2 左右指针刷题

2.1 二分查找

记住模板框架即可。

int binarySearch(vector<int> &nums, int target)
{
	sort(nums.begin(), nums.end());
	int left = 0, right = nums.size() - 1;
	while (left < right)
	{
		int mid = (left + right) / 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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

题解

采用二分查找，具体如下方代码所示。

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //因为数组已经排序好了，所以无需sort
        int left = 0, right = nums.size() - 1;
        int sum = 0;
        vector<int> vec;
        vector<int> res = {-1, -1};
        while (left < right)
        {
            sum = nums[left] + nums[right];
            if (sum == target)
            {
                vec.push_back(left + 1);//下标从1开始，增大下标
                vec.push_back(right + 1);
                return vec;
            }
            if (sum < target)
            {
                ++left;//因为排序好了，小了就移动左指针，大了就移动右指针
            }
            if (sum > target)
            {
                --right;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

结果

2.3 反转字符串

题解

直接左右指针边走边进行交换。

Code

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right)
        {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
        return;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

结果

2.4 最长回文子串

题解

难点在于可以是奇数或者是偶数，找回文串应该是从中心上两边进行扩散。也算是一个算法穷举的思路。

Code

class Solution {
public:
    string longestPalindrome(string s) {
        string res = "";
        for(int i = 0; i < s.length(); i++){
            string s1 = findPalindrome(s, i, i);
            string s2 = findPalindrome(s, i, i+1);
            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }
        return res;
    }

    string findPalindrome(string& s, int l, int r){
        while(l >= 0 && r < s.length() && s[l] == s[r]){
            l--;
            r++;
        }

        return s.substr(l+1, r-l-1); // C++中的子串函数substr(pos, count)，第二参数count是子串长度，l+1是因为while最后一次判断的时候减去了1，所以得加回来。然后substr中的pos相当于起点，count相当于长度，长度=right - left - 1（减去1是因为最后while判断的时候right+1）
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

结果