双指针

通常双指针用于解决滑动窗口问题（子数组），时间复杂度一般为O(n) 如果输入数组对顺序无要求，可以试着先对输入数组快排，尝试从双指针的角度切入 当然双指针问题不一定非得是两个指针，只是这么叫罢了

例题

Two Sum：给定一个数组，找到两个数其和为X 解：

先对数组快排，然后一前一后两个指针求和，大于X则前指针往后移动，小于X则后指针往前移动,时间复杂度O(nlgn),空间复杂度O(1)BitMap，时间/空间复杂度为O(n)

快慢指针找链表中间节点

比较难的题目

三指针992. Subarrays with K Different Integers 多了一个prev指针 class Solution { public: int subarraysWithKDistinct(vector<int>& A, int K) { int i, j, prev, cnt, k, n; n = A.size(); vector<int> f(n+1, 0); for(i = 0,j = 0, cnt = 0, prev = 0, k = 0; j < A.size(); j++){ f[A[j]]++; if(f[A[j]] == 1) k++; if(k > K){ f[A[prev]]--; i = prev + 1; prev = i; k--; } if(k == K){ while(f[A[prev]] != 1){ f[A[prev]]--; prev++; } cnt += prev - i + 1; } } return cnt; } }; 这个题没做出来828. Unique Letter String 需要从存储两个指针 class Solution { public: int uniqueLetterString(string S) { int a[26][2]; int n = S.size(); int ans = 0; int mod = pow(10, 9) + 7; memset(a, -1, 52 * sizeof (int) ); for(int i = 0; i < n; i++){ int c = S[i] - 'A'; ans = (ans + (i - a[c][1]) * (a[c][1] - a[c][0]) % mod) % mod; a[c][0] = a[c][1]; a[c][1] = i; } for(int c = 0; c < 26; c++){ ans = (ans + (n - a[c][1]) * (a[c][1] - a[c][0]) % mod) % mod; } return ans; } }; 这题逆向思维844. Backspace String Compare class Solution { public: bool backspaceCompare(string S, string T) { int i, j; for(i = S.size() - 1, j = T.size() - 1; ; i--, j--){ for(int b = 0; i >= 0 && (b > 0 || S[i] == '#'); i--) b += S[i] == '#' ? 1 : -1; for(int b = 0; j >= 0 && (b > 0 || T[j] == '#'); j--) b += T[j] == '#' ? 1 : -1; if(i < 0 || j < 0 || S[i] != T[j]) return i == -1 && j == -1; } } };

转载于:https://www.cnblogs.com/qbits/p/11056599.html