数组

704. 二分查找

力扣题目链接(opens new window)

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

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例  2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

• 你可以假设 nums  中的所有元素是不重复的。
• n  将在  [1,10000]之间。
• nums  的每个元素都将在  [-9999,9999]之间。

笔记

• 溢出问题（实际数据不会溢出）
• Rust 中将 usize 转换为 i32 类型

C++

class Solution {
public:
  int search(vector<int> &nums, int target) {
    int left = 0;
    int right = nums.size();
    while (left < right) {
      int middle = left + ((right - left) >> 1);
      if (nums[middle] > target) {
        right = middle;
      } else if (nums[middle] < target) {
        left = middle + 1;
      } else {
        return middle;
      }
    }
    return -1;
  }
};

Rust

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len();
        while left < right {
            let middle = left + ((right - left) >> 1);
            if nums[middle] == target {
                return middle as i32;
            } else if nums[middle] < target {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        -1
    }
}

Go

func search(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + ((right - left) >> 1);
        if nums[mid] > target {
            right = mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

27. 移除元素

力扣题目链接(opens new window)

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 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, 3,0, 4。

你不需要考虑数组中超出新长度后面的元素。

笔记

• 数组的位置是可以改变的，使用两个方向的指针处理。
• 对于 Rust 代码，默认可用于访问下标的只有 usize 类型，因此需要保证不小于 0。（这就是我把 C++代码 Copy 过去无法运行的原因……）

C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            while (left <= right && nums[left] != val) {
                left++;
            }
            while (right >= left && nums[right] == val) {
                right--;
            }
            if (left < right) {
                nums[left++] = nums[right--];
            }
        }
        return left;
    }
};

Rust

impl Solution {
pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        if nums.len() == 0 {
            return 0;
        }
        let mut left = 0;
        let mut right = nums.len() - 1;
        while left <= right {
            while left <= right && nums[left] != val {
                left += 1;
            }
            while left <= right && nums[right] == val {
                if right > 0 {
                    right -= 1;
                } else {
                    return 0;
                }
            }
            if left < right {
                nums[left] = nums[right];
                left += 1;
                right -= 1;
            }
        }
        left as i32
    }
}

Go

右指针  right  指向当前将要处理的元素，左指针  left  指向下一个将要赋值的位置。

func removeElement(nums []int, val int) int {
    slow := 0
    for _, fast := range nums {
        if fast != val {
            nums[slow] = fast
            slow++
        }
    }
    return slow
}

977.有序数组的平方

• 力扣题目链接(opens new window)

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

笔记

• 依然需要考虑 Rust 的 usize 类型不能溢出的问题

C++

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result(nums.size());
        int k = nums.size() - 1;
        int i = 0;
        int j = nums.size() - 1;
        while (i <= j) {
            if (nums[i] * nums[i] < nums[j] * nums[j]) {
                result[k--] = nums[j] * nums[j];
                j--;
            } else {
                result[k--] = nums[i] * nums[i];
                i++;
            }
        }
        return result;
    }
};

Rust

impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        if (nums.len() == 0) {
            return nums;
        }
        let mut i = 0;
        let mut j = nums.len() - 1;
        let mut k = nums.len() - 1;
        let mut result = vec![0; nums.len()];

        while i <= j {
            if nums[i] * nums[i] < nums[j] * nums[j] {
                result[k] = nums[j] * nums[j];
                j -= 1;
            } else {
                result[k] = nums[i] * nums[i];
                i += 1;
            }
            if k > 0 {
                k -= 1;
            }
        }
        result
    }
}

Go

func sortedSquares(nums []int) []int {
    n := len(nums)
    i, j, k := 0, n-1, n-1
    ans := make([]int, n)
    for i <= j {
        lm, rm := nums[i]*nums[i], nums[j]*nums[j]
        if lm < rm {
            ans[k] = rm
            j--
        } else {
            ans[k] = lm
            i++
        }
        k--
    }
    return ans
}

209.长度最小的子数组

力扣题目链接(opens new window)

给定一个含有  n  个正整数的数组和一个正整数  s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组  [4,3]  是该条件下的长度最小的子数组。

提示：

• $1 <= target <= 10^9$
• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^5$

笔记：

• 滑动窗口法，时间复杂度为 $O(2n)$
• 官方还提供了二分查找的题解，但可能更难想到
• 个人的理解，这道题可以用滑动窗口的原因，窗口的 start 一旦满足条件，其最佳结果就已经确定了，所以之后都不会再出现，可以排除

C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int min_size = INT32_MAX;
        int current_size = 0;
        int current_sum = 0;
        int i = 0;
        for (int j = 0; j < nums.size(); j++) {
            current_sum += nums[j];
            while (current_sum >= target) {
                current_size = j - i + 1;
                min_size = min_size > current_size ? current_size : min_size;
                current_sum -= nums[i++];
            }
        }
        return min_size == INT32_MAX ? 0 : min_size;
    }
};

Rust

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let mut min_size = i32::MAX;
        let mut current_size = 0;
        let mut current_sum = 0;
        let mut start = 0;
        for (end, num) in nums.iter().enumerate() {
            current_sum += num;
            while current_sum >= target {
                current_size = (end - start + 1) as i32;
                if min_size > current_size {
                    min_size = current_size;
                }
                current_sum -= nums[start];
                start += 1;
            }
        }
        if min_size == i32::MAX {
            return 0;
        }
        min_size
    }
}

Go

func minSubArrayLen(target int, nums []int) int {
    min_size := len(nums) + 1
    current_size, current_sum := 0, 0
    start := 0
    for end := 0; end < len(nums); end++ {
        current_sum += nums[end]
        for current_sum >= target {
            current_size = end - start + 1
            if current_size < min_size {
                min_size = current_size
            }
            current_sum -= nums[start]
            start++
        }
    }
    if min_size == len(nums) + 1 {
        return 0
    }
    return min_size
}

59.螺旋矩阵 II

力扣题目链接(opens new window)

给定一个正整数 n，生成一个包含 1 到 $n^2$ 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3 输出: [[ 1,2, 3 ], [ 8,9, 4 ], [ 7,6, 5 ]]

笔记：

• 模拟题，中间漏考虑了 edge_size 缩小、row 和 col 会自动到下一个位置的问题

Rust

impl Solution {
    pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
        let mut result = vec![vec![0; n as usize]; n as usize];
        let mut element = 1;
        let mut edge_size = (n - 1) as usize;
        let mut round = n / 2;
        let mut has_center = n % 2 == 1;
        let mut row = 0;
        let mut col = 0;

        while round > 0 {
            for offest in 0..edge_size {
                result[row][col] = element;
                element += 1;
                col += 1;
            }
            for offset in 0..edge_size {
                result[row][col] = element;
                element += 1;
                row += 1;
            }
            for offset in 0..edge_size {
                result[row][col] = element;
                element += 1;
                col -= 1;
            }
            for offset in 0..edge_size {
                result[row][col] = element;
                element += 1;
                row -= 1;
            }
            row += 1;
            col += 1;
            round -= 1;
            edge_size -= 2;
        }

        if has_center {
            let mid = (n / 2) as usize;
            result[mid][mid] = element;
        }
        result
    }
}