分別用兩個指標記錄下位置，處理完後移動的做法，叫做Two Pointers，我們用Rust解個幾題熟練一下。

記錄不同陣列的位置

Leetcode 392. Is Subsequence

題目：判斷String s是不是 String t的子序列

輸入：s = "abc", t = "ahbgdc"

輸出：true

限制：

• 0 <= s.length <= 100

• 0 <= t.length <= 10^4

• s and t consist only of lowercase English letters.

做法：將s和t轉成Vec<char>，用指標分別記錄目前兩個向量位置，依序判斷s中的字元是否在String t，如果全部字元依序存在String t回傳true。

impl Solution {
    pub fn is_subsequence(s: String, t: String) -> bool {
        if (s.len()==0) {
            return true
        }
        //check s char from 0 to n-1, if all chars show return true
        let mut s_idx = 0;
        let vec_t:Vec<_>= t.chars().collect();
        let vec_s:Vec<_>= s.chars().collect();
        for c in vec_t {
            if (vec_s[s_idx]==c){
                s_idx+=1;
            }
            if (s_idx== s.len()){
                return true
            }
        }
        false

    }
}

時間複雜度：O(n)，走完vec_t的時間

快慢指標

Leetcode 283. Move Zeroes

題目：將Vec<i32>中0移動到最右側

輸入：nums = [0,1,0,3,12]

輸出：[1,3,12,0,0]

限制：

• 1 <= nums.length <= 10^4

• -2^31 <= nums[i] <= 2^31 - 1

做法：

使用快慢指標，快指標每次往右一格，慢指標當快指標位置的值非0記錄下來，再往右一格，當快指標走完後代表慢指標存下全部非0的值，剩下的位置用0補齊。

impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let mut slow =0;
        let mut fast =0;
        while fast<nums.len(){
            if(nums[fast]!=0){
                nums[slow]=nums[fast];
                slow+=1;
            }

            fast+=1;
        }
        while slow<nums.len(){
            nums[slow]=0;
            slow+=1;
        }
    }
}

時間複雜度：O(n)，走完向量的時間。

左右指標

1679. Max Number of K-Sum Pairs

題目：給一個向量陣列和一個值，在向量陣列中找出有幾對總和等於該值。

輸入：nums = [1,2,3,4], k = 5

輸出：2

限制：

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

• 1 <= k <= 10^9

做法：先對向量陣列排列，用左右指標從最大和最小開始相加，如果和大於k，移動值大的指標往小的值找，反之移動值小的指標往大的值找

impl Solution {
    pub fn max_operations(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort_unstable();
        let mut left = 0;
        let mut right = nums.len() as i32 - 1;
        let mut count = 0;

        while left < right {
            let sum = nums[left as usize] + nums[right as usize];
            if sum == k {
                count += 1;
                left += 1;
                right -= 1;
            } else if sum < k {
                left += 1;
            } else {
                right -= 1;
            }
        }

        count
    }
}

時間複雜度:O(nlogn)
時間複雜度主要由排序O(nlogn)+陣列左右指標找值O(n)，有沒有不用排序就能找到有沒值加起來等於k的解法

1. 看到值(num)在去找對應值(k-num)，跑兩層迴圈時間複雜度就會是O(n^2)

2. 只要跑一次迴圈先建好HashMap，每次都去找是否有(k-num)在map就能知到有幾組和等於k，時間複雜度就會是O(n)

Day4 總結

1. 向量操作
2. 2 Pointers 解題