前言

hello，大家好，這篇博客來介紹LeetCode 20天演算法刷題計劃（點擊跳轉LeetCode20天演算法刷題計劃）第三天的兩道題目，用到的知識點還是雙指標，由于博主個人的懶惰，刷題計劃并沒有每天堅持，雖然內心好像是充滿了愧疚，但還是要繼續懶惰下去哈，
在這里插入圖片描述
好啦，閑言少敘，讓我們開始這篇博客，

1. 283移動零

1.1 題目鏈接

https://leetcode-cn.com/problems/move-zeroes/

1.2 題目描述

給定一個陣列 nums，撰寫一個函式將所有 0 移動到陣列的末尾，同時保持非零元素的相對順序，

在這里插入圖片描述

1.3 題目分析

看到這道題我們首先可以考慮雙指標，左指標指向頭部，右指標指向尾部，右指標不斷向右移動，每次右指標指向非零數，則將左右指標對應的數交換，同時左指標右移，這樣就可以完成交換啦，在這個程序中，左指標以左始終是非0，右指標以右始終是0，在交換程序中，是左指標指向的0元素與右指標指向的非0元素交換，我們來看一下動圖演示（第一次做動圖，質量略顯粗糙）
在這里插入圖片描述
除了這種做法，我們還可以用補0的方法做，也就是說，我們從頭遍歷這個陣列，遇到0我們跳過去，同時我們要記住跳過了幾個0，然后將這些跳過的0在結尾補上，這也是一種實作方法，

1.4 代碼實作

1.4.1 雙指標

void swap(int *a, int *b) {
    int t = *a;
    *a = *b, *b = t;
}

void moveZeroes(int *nums, int numsSize) {
    int left = 0, right = 0;
    while (right < numsSize) {
        if (nums[right]) {
            swap(nums + left, nums + right);
            left++;
        }
        right++;
    }
}

1.4.2 尾部補0

class Solution {
    public void moveZeroes(int[] nums) {
        int indexNow = 0;
        int indexNum = 0;
        int m = nums.length;

        while(indexNum<m){
            if(nums[indexNum] != 0) {
                nums[indexNow++] = nums[indexNum];
            }
            ++indexNum;
        }

        for(int i = indexNow; i < m; i++){
            nums[i] = 0;
        }
    }
}

2. 167. 兩數之和 II - 輸入有序陣列

2.1 題目鏈接

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

2.2 題目描述

給定一個已按照升序排列的整數陣列 numbers ，請你從陣列中找出兩個數滿足相加之和等于目標數 target ，函式應該以長度為 2 的整數陣列的形式回傳這兩個數的下標值，numbers 的下標從 1 開始計數，所以答案陣列應當滿足 1 <= answer[0] < answer[1] <= numbers.length ，
你可以假設每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素，

在這里插入圖片描述

2.3 題目分析

陣列是升序的，這道題我們也是可以用雙指標來解決的，我們依舊設定左指標和右指標，我們讓左指標指向的數字和右指標指向的數字相加，如果相加得到的結果大于target，則右指標向左移動，如果小于則左指標向右移動，如果等于則查找成功，
但是有人可能會疑惑，這種做法會不會存在丟解的情況呢？注意，題目中已經告訴我們是存在唯一解的，也就是說，一定是有固定的兩個位置的值相加等于target，我們的左指標是從小到大，右指標是從大到小，如果我們跳過了作值為例，那么和這個值匹配能夠相加得到target的那個數，一定會比現在右指標指向的那個數大，也就是說，在之前這個數就應該已經和那個數匹配過了，然而并沒有，所以這是一個悖論，所以不存在丟解的情況，
在這里插入圖片描述

2.4 代碼實作

nt* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int* ret = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;

    int low = 0, high = numbersSize - 1;
    while (low < high) {
        int sum = numbers[low] + numbers[high];
        if (sum == target) {
            ret[0] = low + 1, ret[1] = high + 1;
            return ret;
        } else if (sum < target) {
            ++low;
        } else {
            --high;
        }
    }
    ret[0] = -1, ret[1] = -1;
    return ret;
}

后記

好的，這篇博文就到這里了，希望對大家有所幫助，為了更好地完成這篇博客，博主學會了制作動圖，成功get新技能，日拱一卒，繼續努力，
在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/295703.html

標籤：其他

上一篇：震驚！白嫖！使用Github/Gitee搭建基于Hexo的靜態網站服務！

下一篇：資料可視化----ECharts---散點圖（五）

LeetCode 20天演算法刷題計劃第三天：雙指標（2）

目錄

前言