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

Posted on by

前言

雙指針算法

算法思想

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

換言之，雙指針法充分使用瞭數組有序這一特征，從而在某些情況下能夠簡化一些運算。

今天帶大傢來學習算法中雙指針的應用場景。

一、最長不含重復字符的子字符串

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語言 雙指針算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：