詳解C語言中雙指標演演算法的使用

2022-08-18 14:00:02

前言

雙指標演演算法

演演算法思想

雙指標，指的是在遍歷物件的過程中，不是普通的使用單個指標進行存取，而是使用兩個相同方向（快慢指標）或者相反方向（對撞指標）的指標進行掃描，從而達到相應的目的。

換言之，雙指標法充分使用了陣列有序這一特徵，從而在某些情況下能夠簡化一些運算。

今天帶大家來學習演演算法中雙指標的應用場景。

一、最長不含重複字元的子字串

1.題目要求

2.個人題解

2.1 解題思路

利用雙指標，定義一個指標i和一個指標j

讓i開始走，固定住j，然後我們利用一個輔助陣列來記錄下每個字元出現的次數。

比如對於字串“abcabcdd”，當i走到第二個a的時候，a出現了兩次，這時候讓j開始向前走，走到b。

這時候i和j之間的字串是bca。沒有重複的，i可以繼續走，j繼續固定。

i走到b的時候b出現兩次。這時候要移動j直至沒有字元出現次數超過兩次。如此反覆直到i走到字串結尾。

2.2 程式碼實現

class Solution {
public:
    /**
     * 程式碼中的類名、方法名、引數名已經指定，請勿修改，直接返回方法規定的值即可
     *
     * 
     * @param s string字串 
     * @return int整型
     */
    int lengthOfLongestSubstring(string s) {
        int len = s.length();
        int S[128];
        memset(S,0x00, sizeof(S));
        int ans = 0;
        for(int i=0,j=0;i<len;++i)
        {
            S[s.at(i)]++;
            while(S[s.at(i)]>1)
            {
                S[s.at(j)]--;
                j++;
            }
            ans=max(ans,i-j+1); //更新區間最大長度
        }
        return ans;
    }
};

2.3 程式碼解析

首先定義陣列S[128]，利用memset函數來初始化該陣列。

memset：作用是在一段記憶體塊中填充某個給定的值，它是對較大的結構體或陣列進行清零操作的一種最快方法。

for迴圈裡宣告i，j 為0，先讓字串的第一個字元對應的整數作為陣列S的下標，該位置元素值加一；

如果沒有重複字元，ans遞增；如果有重複字元今後進入while迴圈，隨著j的遞增，之前陣列裡為一的元素值都會減一，為2的元素值也會減一併變為一；

接著j固定，i繼續增長，再有重複字元就會重複上述操作，最終通過max函數得到最大的無重複子字串長度。

二、和為S的兩個數位

1.題目要求

2.個人題解

2.1 解題思路

根據題目可知該陣列是升序排列，那我們可以用兩個指標：一個在左邊界，一個在右邊界。

如果陣列下標對應的值相加比num小，那麼就讓左邊指標遞增，反之則右邊指標遞減。

如果左右指標相等，說明沒有滿足條件的數對，返回空陣列。

如果存在該數對，利用push_back方法插入陣列並返回即可

2.2 程式碼實現

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int left,right;
        int i,j,k;
        vector<int> res;
        left=0;
        right=array.size()-1;
        //如果陣列為空,返回空陣列
        if(array.empty()){
            return res;
        }
        while(array[left]+array[right]!=sum && left!=right){
            if(array[left]+array[right]<sum){
                left+=1;
            }else if(array[left]+array[right]>sum){
                right-=1;
            }
        }
        //如果不存在該數對,返回空陣列
        if(left==right){
            return res;
        }
        //如果存在
        res.push_back(array[left]);
        res.push_back(array[right]);
        return res;
    }
};

本題思路確定後程式碼比較好理解，就沒有分析部分了。

這兩道題都是雙指標的解法：第一題相當於是相鄰指標，第二題則是雙端指標，各有特色。

到此這篇關於詳解C語言中雙指標演演算法的使用的文章就介紹到這了,更多相關C語言雙指標演演算法內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

詳解C語言中雙指標演演算法的使用

目錄

前言

一、最長不含重複字元的子字串

1.題目要求

2.個人題解

二、和為S的兩個數位

1.題目要求

2.個人題解

熱門文章