歷經(jīng)時長：7月12日-7月13日

今日總結(jié)：

1. 畫圖呀！不能眼高手低
2. 不要以為雙指針就是頭尾指針，這次的是兩個指針從左至右的快慢指針
3. 雙指針=>想想二分
4. 返回vector可以返回 {1, 2}，不用創(chuàng)建對象
5. 想清楚邏輯關(guān)系

283. 移動零

給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。

// 我寫的，覆蓋（不算是這道題的考點(diǎn)）
// 先遍歷第一次，計算0的個數(shù)，知道元素移動的最終位置
// 遍歷第二次，一一重新賦值，最后的全為0
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        int left = 0, right = len - 1;
        int zero_nums=0;
        for(int i=0; i <= right; ++i){
            if(nums[i]==0) zero_nums++;
        }
        for(int i=0,j=0; i<=right; ++i){
            if(j==(len-zero_nums)) break;
            if(nums[i]==0)      continue;
            nums[j++]=nums[i];
        }
        for(int i=right; i>=len-zero_nums; i--){
            nums[i]=0;
        }
    }
};

//這道題叫交換0
//雙指針方法，快慢指針，這是官方解題
void moveZeroes(vector<int>& nums) {
        int len = nums.size(), left = 0, right = 0;
        while (right<len)
        {
            if (nums[right])
            {
                swap(nums[left++], nums[right]);
            }
            right++;
        }

167. 兩數(shù)之和 II - 輸入有序數(shù)組

給定一個已按照 升序排列 的整數(shù)數(shù)組 numbers ，請你從數(shù)組中找出兩個數(shù)滿足相加之和等于目標(biāo)數(shù) target 。

函數(shù)應(yīng)該以長度為 2 的整數(shù)數(shù)組的形式返回這兩個數(shù)的下標(biāo)值。numbers 的下標(biāo) 從 1 開始計數(shù) ，所以答案數(shù)組應(yīng)當(dāng)滿足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假設(shè)每個輸入只對應(yīng)唯一的答案，而且你不可以重復(fù)使用相同的元素。

在數(shù)組中找到兩個數(shù)，使得它們的和等于目標(biāo)值，可以首先固定第一個數(shù)，然后尋找第二個數(shù)，第二個數(shù)等于目標(biāo)值減去第一個數(shù)的差。利用數(shù)組的有序性質(zhì)，可以通過二分查找的方法尋找第二個數(shù)。為了避免重復(fù)尋找，在尋找第二個數(shù)時，只在第一個數(shù)的右側(cè)尋找。

// 方法一：二分查找
// 先固定一個數(shù)，二分查找另一個數(shù)
vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i=0; i<numbers.size(); ++i){
            int low=i+1, high=numbers.size()-1;  // 這里要注意！兩個指針要指對位置
            int tar = target-numbers[i];
            int mid;
            while(low<=high){  // 注意這里！！結(jié)束條件要牢記，<=
                mid = (high - low) / 2 + low;  // 注意！記得加low
                if(numbers[mid]>tar) high=mid-1;
                else if(numbers[mid]<tar) low=mid+1;
                else return {i+1, mid+1};
            }
        }
        return {-1, 1};
    }

// 方法二：雙指針
vector<int> twoSum(vector<int>& numbers, int target) {
        int left=0, right=numbers.size()-1;
        while(left<right){
            if(numbers[left]+numbers[right]>target) right--;
            else if(numbers[left]+numbers[right]<target) left++;
            else return {left+1,right+1};
        }
        return {-1, 1};
    }