九十六、双指针和滑动窗口算法模板

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        
        if (fast && fast->next){
            slow = head;
            while(slow!=fast){
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
        return nullptr;
    }
};

def threeSum(nums):
    nums.sort()
    # [-4, -1, -1, 0, 1, 2]
    res_list = []
    # 头部循环查找
    for i in range(len(nums)):
     #  必须判断 nums[i] > nums[i - 1]这个条件
        if i == 0 or nums[i] > nums[i - 1]:
            # 最左端
            l = i + 1
            # 最右端
            r = len(nums) - 1
            while l < r:  # 正在查找
                three_sum = nums[i] + nums[l] + nums[r]
                if three_sum == 0:
                    res_list.append([nums[i], nums[l], nums[r]])
                    l += 1  # 右移一位
                    r -= 1  # 左移一位
                    while l < r and nums[l] == nums[l - 1]:
                        # 从左往右，相同数值直接跳过
                        l += 1
                    while r > l and nums[r] == nums[r + 1]:
                        # 从右往左，相同数值直接跳过
                        r -= 1
                elif three_sum > 0:
                    # 大于零，右边数值大，左移
                    r -= 1
                else:
                    # 小于零，左边数值小，右移
                    l += 1
    return res_list

def binary_search(nums, target):
 '''标准二分算法模板'''
    low = 0
    high = len(nums) - 1  # 注意1 low和high用于跟踪在其中查找的列表部分
    while low <= high:  # 注意2 只要还没有缩小到只有一个元素，就不停的检查
        mid = (low + high) // 2
        if list[mid] == target:
            return mid
        elif list[mid] > target:
            high = mid - 1  # 注意3 猜的数字大了
        elif list[mid] < target:
            low = mid + 1   # 注意4 猜的数字小了
    return mid


def bsearch_low(nums,target):
    '''求第一个等于定值 '''
    low = 0
    high = len(nums) - 1
    # 这里需要 <=
    while low <= high:
        # 这里需要注意： 就是使用((high - low) >> 1)需要双扩号
        mid = low + ((high - low) >> 1)
        if nums[mid] < target:
            low = mid + 1
        elif nums[mid] > target:
            high = mid - 1
        else:
            if mid == 0 or nums[mid-1] != target:
                return mid
            else:
                high = mid -1

    return -1

def bsearch_high(nums,target):
    '''求最后一个等于定值的'''
    low = 0
    higt = len(nums) -1
    while low <= higt:
        mid = low + ((higt- low) >>1 )
        if nums[mid] > target:
            higt = mid - 1
        elif nums[mid] < target:
            low = mid +1
        else:
            if mid == (len(nums) -1) or nums[mid] != nums[mid+1]:
                return mid
            else:
                low = mid +1
    return  -1

'''
查找第一个大于等于给定值的元素
* 如序列：3，4，6，7，19 查找第一个大于5的元素，即为6，return 2
* 第一个大于给定值，则说明上一个小于给定值，依次判断
'''
def bsearch_low_not_less(nums,target):
    low = 0
    high = len(nums) -1
    while(low<=high):
        mid = low + ((high-low) >>1)
        if nums[mid] >= target:
            if mid == 0 or nums[mid - 1] < target:
                return mid
            else:
                # 往左移动
                high = mid - 1
        else:
            # 往右移动
            low = mid +1
    return -1

'''
查找第一个小于给定值的元素
* 如序列：3，4，6，7，19 查找第一个小于5的元素，即为4，返回1
* 第一个大于给定值，则说明上一个小于给定值，依次判断
'''
def bsearch_high_not_greater(nums,target):
    '''求最后一个小于等于值'''
    low = 0
    higt = len(nums) -1
    while low <= higt:
        mid = low + (( higt -low ) >> 1)
        if nums[mid] <= target:
            if (mid == len(nums) -1) or (nums[mid + 1] > target):
                return mid
            else:
                low = mid +1
        else:
            higt = mid -1
    return  -1

/* 滑动窗口算法框架 */
string minWindow(string s, string t) {
     // 两个unordered_map ，一个need记录模式串的字符数量，一个window记录窗口的字符
    unordered_map<char, int> need, window;
    // 初始化need
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    // 两个unordered_map的符合条件数目
    int valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    int start = 0, len = INT_MAX;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (valid == need.size()) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }                    
        }
    }
    // 返回最小覆盖子串
    return len == INT_MAX ?
        "" : s.substr(start, len);
}