Easy

题目描述

一只蚂蚁在边界上。它有时向左走，有时向右走。

给你一个非零整数数组 nums。蚂蚁从数组的第一个元素开始读取，直到结束。在每一步中，它根据当前元素的值移动：

  • 如果 nums[i] < 0，它向左移动 -nums[i] 个单位。
  • 如果 nums[i] > 0，它向右移动 nums[i] 个单位。

返回蚂蚁返回边界的次数。

注意：

  • 边界两侧都有无限的空间。
  • 我们只在蚂蚁移动了 |nums[i]| 个单位后检查它是否在边界上。换句话说，如果蚂蚁在移动过程中穿过了边界，这不会被计算在内。

示例 1：

输入：nums = [2,3,-5]
输出：1
解释：第一步后，蚂蚁在边界右侧 2 步。
第二步后，蚂蚁在边界右侧 5 步。
第三步后，蚂蚁在边界上。
所以答案是 1。

示例 2：

输入：nums = [3,2,-3,-4]
输出：0
解释：第一步后，蚂蚁在边界右侧 3 步。
第二步后，蚂蚁在边界右侧 5 步。
第三步后，蚂蚁在边界右侧 2 步。
第四步后，蚂蚁在边界左侧 2 步。
蚂蚁从未返回边界，所以答案是 0。

约束：

  • 1 <= nums.length <= 100
  • -10 <= nums[i] <= 10
  • nums[i] != 0

解题思路

这道题是一个简单的模拟问题，我们需要跟踪蚂蚁的位置并计算它返回边界（位置为0）的次数。

解题思路：

  1. 蚂蚁从边界（位置0）开始
  2. 维护一个位置变量，记录蚂蚁当前的位置
  3. 对数组中的每个元素，将其值加到位置变量上
  4. 每次移动后检查位置是否为0，如果是则计数器加1
  5. 返回总的计数次数

具体步骤：

  • 初始化位置position = 0和计数器count = 0
  • 遍历数组中的每个数字
  • 将数字加到position上（正数向右移动，负数向左移动）
  • 如果移动后position等于0，说明回到边界，count加1
  • 最后返回count

这个解法的时间复杂度是O(n)，空间复杂度是O(1)，其中n是数组的长度。算法非常直接，就是按题目要求模拟蚂蚁的移动过程。

代码实现

class Solution {
public:
    int returnToBoundaryCount(vector<int>& nums) {
        int position = 0;
        int count = 0;
        
        for (int num : nums) {
            position += num;
            if (position == 0) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def returnToBoundaryCount(self, nums: List[int]) -> int:
        position = 0
        count = 0
        
        for num in nums:
            position += num
            if position == 0:
                count += 1
        
        return count

public class Solution {
    public int ReturnToBoundaryCount(int[] nums) {
        int position = 0;
        int count = 0;
        
        foreach (int num in nums) {
            position += num;
            if (position == 0) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var returnToBoundaryCount = function(nums) {
    let position = 0;
    let count = 0;
    
    for (let i = 0; i < nums.length; i++) {
        position += nums[i];
        if (position === 0) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(n)
空间复杂度O(1)

其中 n 是数组 nums 的长度。我们只需要遍历数组一次，每次操作都是常数时间，因此时间复杂度为 O(n)。只使用了常数个变量来存储位置和计数，所以空间复杂度为 O(1)。