指针专题

15. 三数之和
    首先固定一个数，然后另外两个数用两个指针去探索记录和为0的组合。
    对于前后一样的数可以跳过

c++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int target;
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
             target= nums[i];
             if (target > 0) break;
             if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                if (nums[l] + nums[r] + target < 0) ++l;
                else if (nums[l] + nums[r] + target > 0) --r;
                else {
                    ans.push_back({target, nums[l], nums[r]});
                    ++l, --r;
                    while (l < r && nums[l] == nums[l - 1]) ++l;
                    while (l < r && nums[r] == nums[r + 1]) --r;
                }
            }
        }
        return ans; 
    }
};

二、滑动窗口
3. 无重复字符的最长子串
滑动窗口的本质也是双指针,两个指针分别代表某个子串的两端，用ss这个字典来表示某个字符最新出现的位置，当右指针遍历到一个新字符，就检查一下这个元素最新的位置c，这个新串的起始位置就是c+1，每一个窗口就比较一下获得最大值。

c++

class Solution {
public:
     int lengthOfLongestSubstring(string s) {
        map<char, int>ss;
        int max_len = 0;
        int left = 0;
        for (int j = 0; j < s.size(); j++) {
            if (ss.find(s[j]) != ss.end()) {
                left = max(left, ss[s[j]] + 1);
            }
            int cur_len = j - left + 1;
            if (max_len < cur_len)
                max_len = cur_len;
            if (ss.find(s[j]) != ss.end())
                ss.erase(s[j]);
            ss[s[j]] = j;
        }
        return max_len;
    }
};