0.理论基础

• 数组在内存空间的地址是连续的
• 数组中的元素只能覆盖，不能删除

1.循环不变量

leetcode：704.二分查找

【题目描述】

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target， 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

【示例】

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1

【思路】

升序数组，元素无重复，可以用二分查找。二分查找思路很简单，但边界控制容易出错，对区间的定义不清楚。
二分查找的区间定义一般有两种：左闭右闭，左闭右开

// C++
int search(vector<int>& nums, int target) {
    if (nums.size() <= 0)
        return -1;

    int left = 0;
    int right = nums.size() - 1;

    while (right >= left)   // 左闭右闭
    {
        int mid = (right + left) / 2; // 索引
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

// python
def search(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while right >= left:
        mid = (right + left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return -1

2.双指针法

leetcode:27.移除元素

【题目描述】

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

【示例】

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]

【思路】

1. 暴力解法：两个 for 循环，第一个循环遍历数组，第二个循环移动数组
2. 双指针（快慢指针）：快指针，遍历数组; 慢指针，维持当前数组中慢指针之前区间所有元素不等 val; 当快指针遇到不等于 val 值的元素时，交换至慢指针，慢指针再移动一次
3. 双指针（首尾指针）：首指针，从前往后遍历；尾指针，从后往前遍历，直至首尾指针相遇。当首指针等于 val 时，将尾指针的值交换至首指针，尾指针前移，首指针值不等于 val 时后移

// C++
// 快慢指针
int removeElement2(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;   // 不需要 +1
}

// 首尾双指针，能避免不必要的移动
int removeElement(vector<int> &nums, int val)
{
    int firstIndex = 0;
    int lastIndex = nums.size() - 1;

    while (firstIndex <= lastIndex)
    {
        if (nums[firstIndex] == val)
        {
            int temp = nums[firstIndex];
            nums[firstIndex] = nums[lastIndex];
            nums[lastIndex] = nums[firstIndex];
            lastIndex--;
        }
        else
            firstIndex++;
    }
    return firstIndex;

# python
def remove_element(nums: List[int], val: int) -> int:
    slow_index = 0
    for fast_index in range(0, len(nums)):
        if val != nums[fast_index]:
            nums[slow_index] = nums[fast_index]
            slow_index += 1
    return slow_index


def remove_element2(nums: List[int], val: int) -> int:
    last_index, first_index = len(nums) - 1, 0
    while first_index < last_index:
        if nums[first_index] == val:
            nums[first_index] = nums[last_index]
            last_index -= 1
        else:
            first_index += 1
    return first_index

3. 滑动窗口

leetcode:209.长度最小的子数组
【题目描述】

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

【示例】

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

【思路】

1. 暴力解法：两个 for 循环
2. 滑动窗口

// C++
/**
 * 滑动窗口 3 要素：
 * 1. 窗口内元素
 * 2. 如何移动窗口起始位置？
 * 3. 如何移动窗口终止位置？
 * 
 * 本题：
 * 1. 窗口内是和大于等于 target 的元素
 * 2. 移动起始位置：当前窗口和大于等于 target
 * 3. 移动终止位置：当前窗口和小于 target
 * 通过终止位置遍历指针
 */ 
int minSubArrayLen(int target, vector<int>& nums) {
    int result = __INT32_MAX__;
    int sum = 0;
    int subLength = 0;
    int startIndex = 0;
    for (size_t i = 0; i < nums.size(); i++)
    {
        sum += nums[i];
        while ( sum >= target ){
            subLength = i - startIndex + 1;
            result = result < subLength ? result : subLength;
            sum -= nums[startIndex++];
        }
    }
    return result == __INT32_MAX__ ? 0 : result; 
}

# python
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    result = sys.maxsize
    start_index, sub_length, sum = 0, 0, 0
    for i in range(0, len(nums)):
        sum += nums[i]
        while sum >= target:
            sub_length = i - start_index + 1
            result = result if result < sub_length else sub_length
            sum -= nums[start_index]
            start_index += 1