尺取法（双指针）

尺取法，顾名思义，就是用一把尺子，不断向右移动，在移动过程中维护某一性质并更新答案的方法，这种方法一般用来求满足某一条件的最短区间。

参考博客（链接）：点我跳转
实现步骤：

• 1.初始化左右端点
• 2.不断扩大右端点，直至满足条件
• 3.如果直至终点也无法满足条件，则终止，否则更新结果
• 4.扩大左端点（右移1），跳回步骤2

从一个例题来认识一下此过程(网上举得例子好像都是这个):

poj3601

大致题意：给定一个数组，再给定一个整数s，求数组中的一个最短连续序列，要求该序列和大于等于s

这里借助https://blog.csdn.net/weixin_41162823/article/details/80328404
的图片演示：

pic

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5+100;

int t,n,s;
long long a[N];

int main()
{
    cin>>t;
    while(t--){
        cin>>n>>s;
        for(int i = 1; i<=n; i++) cin>>a[i];
        
        long long l = 1,r = 1,sum = 0,res = N;
        while(1){
            while(r <= n && sum < s) sum += a[r++];  //步骤2
            if(sum < s) break;                       //步骤3
            res = min(res,r-l);
            sum -= a[l++];                          //步骤4
        }
        if(res == N) cout<<0<<endl;
        else cout<<res<<endl;
    }
    return 0;
}

---

update on 2020/06/12

LeetCode15.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

solution：

答案中不可以包含重复的三元组，所以我们可以对数组先排序，与两数之和不同的是，这里要找到三个数，其和为0，可以做一个转化，固定a，那么找b+c=-a即可，这就转换成了两数之和的问题，因为每次b向后枚举，数组是从小到大排列的，所以c不会比上次的c大，那么可以利用双指针来做，c从后向前遍历，b从a的后面向后遍历，找到两数之和为-a，时间复杂度为。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //solution: 先对数组排序，固定a，向后枚举b因为每次b会增大，所以可以从后向前找c
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        if(!n) return ans;

        if(nums[0] > 0) return ans;
        
        for(int a = 0; a<n; a++){
            if(a>0 && nums[a] == nums[a-1]) continue;

            int sum = -nums[a];
            int c = n-1;

            for(int b = a+1; b<n; b++){
                if(b > a+1 && nums[b] == nums[b-1]) continue;

                while(b < c && nums[b] + nums[c] > sum) -- c;

                if(b == c) break;

                if(nums[b] + nums[c] == sum){
                    ans.push_back({nums[a], nums[b], nums[c]});
                }
            }
        }
        return ans;
    }
};