はじめに

ダブルポインタの問題を解決するための3つの一般的なアイデア：

左ポインタと右ポインタ：2つのポインタが必要で、1つは先頭を指し、もう1つは末尾を指し、条件が満たされるか、2つのポインタが出会うまで途中までトラバースします。 高速ポインタと低速ポインタ：2つのポインタが必要で、どちらも先頭で先頭を指し、条件が異なると、条件が満たされるか、高速ポインタが末尾に行くまで、高速ポインタは高速に、低速ポインタは低速に進みます。 後方ポインタ：通常のポインタ操作は、マージと置換のために前方から後方へ促進されます。マージと置換タイプの問題では、データが上書きされるのを防ぐために、ダブルポインタを後ろから前に移動させる必要があります ニーモニック：クリップの真ん中に左右のポインタ、後置ポインタの最後に高速ポインタと低速ポインタが後方に移動します

ツー・ポインター・テクニック - シナリオ1

いくつかの問題は、配列を繰り返し処理することで解決します。通常、反復処理に必要なポインタは1つだけです。つまり、配列の最初の要素から始まり、最後の要素で終わります。しかし、2つのポインタを使用することもあります。

例題

古典的な問題から始めましょう：

配列の要素を反転します。 ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e'] ['e', 'd', 'o', 'c', 't', 'e', 'e', 'l']例えば、配列が , の場合、反転後はこのようになります。

ダブル・ポインタの使い方は、2つのポインタをそれぞれ配列の先頭と末尾に置き、それらのポインタが指す要素を入れ替えます。

def reverseString(self, s):
 i, j = 0, len(s) - 1
 while i < j:
 s[i], s[j] = s[j], s[i]
 i += 1
 j -= 1

概要

要約すると、ダブル・ポインターを使う典型的なシナリオの1つは、次のような場合です。

配列の両端から中央に向かって繰り返します。

ここでダブルポインタのトリックが使えます：

一方のポインターは頭から、もう一方のポインターは尻尾から。

このテクニックはソートされた配列でよく使われます。

ツー・ポインター・テクニック - シナリオ2

この問題は、2つの非同期ポインタ、つまり高速ポインタと低速ポインタを使うことで解決できることがあります。シナリオ1とは異なり、2つのポインタは反対ではなく同じ方向に動きます。

例題

古典的な問題から始めましょう：

配列 nums と値 val が与えられた場合、 val と等しい要素をすべて削除し、削除後の配列の新しい長さを返す必要があります。

スペースの複雑さの制約がなければ、もっと簡単です。新しい配列を初期化して、答えを格納することができます。要素が指定された目標値と等しくない場合は、元の配列を繰り返し処理し、要素を新しい配列に追加します。

事実上、これは2つのポインタを使うのと同じことで、1つは元の配列の反復処理に使い、もう1つは常に新しい配列の最後の位置を指しています。

スペースの制約を考慮

余分な配列を使わず、元の配列だけを操作する場合は？

この場合、高速ポインタと低速ポインタという考え方を使うことができます。高速ポインタfastと低速ポインタslowを初期化し、fastが指す値がvalと等しくない場合にのみ1ステップずつ移動します。

短い

これも、ダブルポインタのトリックを使う必要がある非常に一般的な状況です：

遅いポインターと速いポインターがあります。

このような問題を解決する鍵は

2つのポインターの移動戦略を決定します。

前のシナリオと同様に、ダブルポインタのトリックを使いながら配列をソートする必要がある場合もありますし、移動戦略を決定するために強欲の法則を適用する必要がある場合もあります。

パワーバックルトピックの例

ダブルポインタの左右ポインタに関する話題：

1. Two Sum II - Input array is sorted

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

1. Sum

class Solution {
public:
 vector<vector<int>> threeSum(vector<int>& nums) {
 vector<vector<int>> res;
 int n = nums.size();
 if(n <= 2) return res;
 sort(nums.begin(), nums.end());
 for(int i = 0; i < n-2; i++){
 int left = i + 1, right = n - 1;
 while(left < right){
 int temp = nums[left] + nums[right];
 if(temp > -nums[i]){
 right--;
 }else if(temp < -nums[i]){
 left++;
 }else{
 vector<int> tmp{nums[i], nums[left], nums[right]};
 res.push_back(tmp);
 left++;
 right--;
 while(left < right && nums[left] == nums[left - 1]) left++;
 while(left < right && nums[right] == nums[right + 1]) right--;
 }
 }
 while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
 }
 return res;
 }
};

1. Sum Closest

class Solution {
public:
 int threeSumClosest(vector<int>& nums, int target) {
 int n = nums.size(), res = INT_MIN, small = INT_MAX;
 sort(nums.begin(), nums.end());
 for(int i = 0; i < n-2; i++){
 int left = i + 1, right = n - 1;
 while(left < right){
 int temp = nums[left] + nums[right] + nums[i];
 if(abs(temp - target) < small){
 res = temp;
 small = abs(temp - target);
 }
 if(temp > target){
 right--;
 }else if(temp < target){
 left++;
 }else{
 return target;
 }
 }
 while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
 }
 return res;
 }
};

1. Sum

n 個の整数からなる配列 nums と 1 つの整数 target が与えられたとき， a + b + c + d = target となるような要素 a, b, c, d が nums 内にありますか？ target の和を与える配列中の一意な四則演算をすべて求めなさい．ターゲットの和を与える配列。 問題の要件：n 個の整数と 1 つの整数のターゲットの配列が与えられたとき、a + b + c + d = ターゲットとなるような要素 a, b, c, d が nums 内にありますか？ 配列内のすべての一意な四重項を求めなさい。注意：解答には重複した四元数を含んではいけません。トピックの分析：前回の15.3Sumに基づいて、4つの数の和の問題を2つの数の和の問題に変換しようとするのは少し難しい：再び、最初の配列をソートし、4つのポインタk、i、左、右、最初の番号を指すようにkのポインタを設定し、iのポインタは、2番目の番号を指すように、その後、左、右の2つの配列の残りの数を指すように、このように2つの数の和に変換質問タイトルの答え

class Solution {
public:
 vector<vector<int>> fourSum(vector<int>& nums, int target) {
 vector<vector<int>> res;
 int n = nums.size();
 if(n <= 3) return res;
 sort(nums.begin(), nums.end());
 for(int k = 0; k < n-3; k++){
 for(int i = k + 1; i < n-2; i++){
 int left = i + 1, right = n - 1;
 int ret = target - nums[k] - nums[i];
 while(left < right){
 int temp = nums[left] + nums[right];
 if(temp > ret){
 right--;
 }else if(temp < ret){
 left++;
 }else{
 vector<int> tmp{nums[k], nums[i], nums[left], nums[right]};
 res.push_back(tmp);
 left++;
 right--;
 while(left < right && nums[left] == nums[left - 1]) left++;
 while(left < right && nums[right] == nums[right + 1]) right--;
 }
 }
 while(i + 1 < n -2 && nums[i] == nums[i + 1]) i++;
 }
 while(k + 1 < n -3 && nums[k] == nums[k + 1]) k++;
 } 
 return res;
 }
};

1. Container With Most Water

n 個の非負整数 a1, a2, ... が与えられたとします．ここで，各点は座標 ． x軸とともに容器を形成する2つの直線を求めなさい。 x軸と一緒になって容器を形成し，その容器が最も多くの水を含むような2本の直線を求めなさい． 問題文：n個の非負整数a1, a2, ... , anが与えられ，それぞれが座標.また，an はそれぞれ座標軸上の高さを表します．この配列は、任意の2つの列がバケツを形成する棒グラフの構築に基づくことができ、要件は、最も多くの水を保持することができるバケツの面積を見つけることです。トピックの分析：2つの垂直線とX軸は容器を形成し、どのくらいの水が充填されるだけでなく、2つの列の高さに関連していないだけでなく、2つの列の間の距離に関連している、式：S（i,j）= min（ai,aj） * 、容器は、最も水を保持する2つの行の組み合わせを見つけるために、傾けることはできません。左と右の2つのポインタは、配列の左端と右端を指すように定義し、その後、検索の真ん中に2つのポインタは、すべての移動が値をカウントし、結果が大きい方を取るために比較され、コンテナは、アルゴリズムが2つのエッジ間の距離を乗じた左右のエッジの小さい方を見つけることです水の量を保持 トピックの答え：

class Solution {
public:
 int maxArea(vector<int>& height) {
 int left = 0, right = height.size() - 1;
 int res = 0;
 while(left < right){
 int temp = min(height[right], height[left]);
 res = max(res, temp*(right - left));
 if(height[right] < height[left]) right--;
 else left++;
 }
 return res;
 }
};

1. Trapping Rain Water

各棒の幅が 1 である標高マップを表す n 個の非負整数が与えられたとき、それが雨の後に閉じ込めることができる雨水の量を計算しなさい：各要素がポスターの標高を表し、各要素の幅が 1 である配列が与えられたとき、雨が降った後にどれだけの雨水を閉じ込めることができるかを計算しなさい。トピック分析：一度だけトラバースする必要がある解決策を見て、このアルゴリズムは、2つのポインタの現在の範囲で、両側からスキャンの途中まで、配列の最初と最後の位置を指す左と右の2つのポインタを必要とする小さい方の値を見つけるために、最初の2つの比較の範囲を決定するために、もし小さい方の値は、左から右へのスキャンの値を指す左の値である場合、右から左へのスキャンの値を指す右の値である場合、遭遇した値は、右から左へのスキャンの値である場合、遭遇した値は、右から左へのスキャンの値である場合、遭遇した値は、右から左へのスキャンの値である場合よりも多い場合。スキャンは、もし遭遇した値より小さい値が小さい場合、差が結果に堆積され、そのような遭遇した値が大きい場合、新しいウィンドウのスコープを再定義し、左と右のポインタが一致するまでなど。タイトルの解決策

class Solution {
public:
 int trap(vector<int>& height) {
 int res = 0, left = 0, right = height.size() - 1;
 int maxleft = 0, maxright = 0;
 while(left < right){
 if(height[left] < height[right]){
 if(height[left] > maxleft){
 maxleft = height[left];
 }else{
 res += maxleft - height[left];
 }
 left++;
 }else{
 if(height[right] > maxright){
 maxright = height[right];
 }else{
 res += maxright - height[right];
 }
 right--;
 }
 }
 return res;
 }
};

ダブルポインタの高速ポインタと低速ポインタに関する話題：

ダブルポインタの高速ポインタと低速ポインタに関する話題：

1. Remove Element

class Solution {
public:
 int removeElement(vector<int>& nums, int val) {
 int slow = 0, fast = 0, n = nums.size();
 while(fast < n){
 if(nums[fast] != val) nums[slow++] = nums[fast];
 fast++;
 }
 return slow;
 }
};

1. Move Zeroes

配列 nums が与えられた場合、0 以外の要素の相対的な順序を維持したまま、すべての 0 をその配列の最後に移動する関数を書きなさい。 問題の要求:この問題は、与えられた配列内のすべての 0 を、0 以外の要素の相対的な順序を維持したまこの問題では、非ゼロ要素の相対的な順序を維持しながら、与えられた配列内のすべての0を最後まで移動させます。トピックの分析: 0に等しくない整数が配列の前部に移るように、遅いおよび速いポインターの使用、頭部からの横断、速いポインターの前方への横断、要素が0に等しくないとき、遅いポインターの前方への横断。質問の答え

class Solution {
public:
 void moveZeroes(vector<int>& nums) {
 int slow = 0, fast = 0, n = nums.size();
 while(fast < n){
 if(nums[fast] != 0) swap(nums[slow++], nums[fast]);
 fast++;
 }
 }
};

1. Remove Duplicates from Sorted Array

ソートされた配列numsが与えられた場合、各要素が一度だけ表示されるように、インプレースで重複を削除し、新しい長さを返します.题要求：这道题要从有序数组中去除重复项。トピック分析：この問題の解決策は、2つのポインタの先頭の座標の走査を記録するために、高速および低速ポインタを使用することです数字の数を指すように高速ポインタは、最初の1の前に低速ポインタと等しい場合は、2つのポインタを1歩進め、異なる場合は、高速ポインタは、配列全体を通過するように、低速ポインタは、異なる数字の数の配列の現在の座標です。トピックの答え：

class Solution {
public:
 int removeDuplicates(vector<int>& nums) {
 int slow = 1, fast = 1, n = nums.size();
 if(n <= 1) return n;
 while(fast < n){
 if(nums[fast] != nums[slow - 1]) nums[slow++] = nums[fast];
 fast++;
 }
 return slow;
 }
};

1. Remove Duplicates from Sorted Array II

ソートされた配列 nums が与えられたとき、重複が最大2回出現するように重複をインプレースで削除し、新しい長さを返します。 問題の要求：この問題では、順序付き配列から重複を削除します。この問題では、各数字が最大2回出現するように、順序付き配列から重複を削除する必要があります。トピックの分析：と前の解決策は、トラバーサル座標を記録するために、高速および低速ポインタを使用してのアイデアに似ている、2つのポインタの先頭は、最初の2つの数字への低速ポインタに等しい数への高速ポインタは、その後、高速ポインタを1歩進め、異なる場合は、2つのポインタを1歩進め、高速ポインタが配列全体を歩くように、配列の現在の座標への低速ポインタは、異なる番号の数です。トピックの答え

class Solution {
public:
 int removeDuplicates(vector<int>& nums) {
 int slow = 2, fast = 2, n = nums.size();
 if(n <= 2) return n;
 while(fast < n){
 if(nums[fast] != nums[slow - 2]) nums[slow++] = nums[fast];
 fast++;
 }
 return slow;
 }
};

1. Find the Duplicate Number

各整数が 1 から n(包含)までの n + 1 個の整数を含む配列 nums が与えられたとき，重複する数が少なくとも 1 つ存在することを証明しなさい． 重複する数が 1 つだけあると仮定しなさい．重複数が1つしかないと仮定して、重複数を求めなさい。题要求：在一个长度为n+1的数组中，每数都是1-n之间，只有一个出现两次，其他的数都只出现一次，找出这个数。トピック分析：高速ポインタと低速ポインタの核心的なアイデアは、タイトルのように区間[1,n]に限定されるので、巧みに互いの間の座標と値を使用することができ、繰り返される数の存在のために、それは確かにリングを形成し、高速ポインタと低速ポインタがリングを見つけることができ、リングの開始位置を決定し、それは確かにあまりにも巧妙です！タイトルの答え

class Solution {
public:
 int findDuplicate(vector<int>& nums) {
 int slow = nums[0], fast = nums[nums[0]];
 while(slow != fast){
 slow = nums[slow];
 fast = nums[nums[fast]];
 }
 fast = 0;
 while(slow != fast){
 slow = nums[slow];
 fast = nums[fast];
 }
 return slow;
 }
};

ダブル・ポインタに続くシーケンシャル・ポインタに関するトピック：

ダブル・ポインタに続くシーケンシャル・ポインタに関するトピック：

1. Merge Sorted Array

2つの並べ替えられた整数配列nums1とnums2が与えられたとき、nums2を1つの並べ替えられた配列としてnums1にマージしなさい。 問題の定義：2つの並べ替えられた整数配列nums1とnums2が与えられたとき、nums2をnums1にマージし、nums1が並べ替えられた配列になるようにしなさい。配列になります。nums1 には nums2 の要素を保持するのに十分なスペースがあると仮定してかまいません。マージされた配列 A のサイズは m+n でなければならないので、一番後ろから始めて、A と B の最後の要素のサイズを比較しながら前に進みます。もしAのすべての要素がBより小さければ、最初のm個はそのままAの元の内容です。Aの配列がBより大きい場合、Aのループが終了し、BにまだAに追加されていない要素があるとき、ループを直接使用して、Bのすべての要素をAの残りの位置で上書きします。質問の答え

class Solution {
public:
 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
 int i = m - 1, j = n - 1, k = m + n -1;
 while(i >= 0 && j >= 0){
 if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
 else nums1[k--] = nums2[j--];
 }
 while(j >= 0) nums1[k--] = nums2[j--];
 }