README.md

comments	difficulty	edit_url	rating	source	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3000-3099/3028.Ant%20on%20the%20Boundary/README.md	1115	第 383 场周赛 Q1	数组 前缀和 模拟

3028. 边界上的蚂蚁

English Version

题目描述

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

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

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

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

注意：

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

 

示例 1：

输入：nums = [2,3,-5]
输出：1
解释：第 1 步后，蚂蚁距边界右侧 2 单位远。
第 2 步后，蚂蚁距边界右侧 5 单位远。
第 3 步后，蚂蚁位于边界上。
所以答案是 1 。

示例 2：

输入：nums = [3,2,-3,-4]
输出：0
解释：第 1 步后，蚂蚁距边界右侧 3 单位远。
第 2 步后，蚂蚁距边界右侧 5 单位远。
第 3 步后，蚂蚁距边界右侧 2 单位远。
第 4 步后，蚂蚁距边界左侧 2 单位远。
蚂蚁从未返回到边界上，所以答案是 0 。

 

提示：

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

解法

方法一：前缀和

根据题目描述，我们只需要计算 $nums$ 的所有前缀和中有多少个 $0$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为 $nums$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def returnToBoundaryCount(self, nums: List[int]) -> int:
        return sum(s == 0 for s in accumulate(nums))

Java

class Solution {
    public int returnToBoundaryCount(int[] nums) {
        int ans = 0, s = 0;
        for (int x : nums) {
            s += x;
            if (s == 0) {
                ++ans;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int returnToBoundaryCount(vector<int>& nums) {
        int ans = 0, s = 0;
        for (int x : nums) {
            s += x;
            ans += s == 0;
        }
        return ans;
    }
};

Go

func returnToBoundaryCount(nums []int) (ans int) {
	s := 0
	for _, x := range nums {
		s += x
		if s == 0 {
			ans++
		}
	}
	return
}

TypeScript

function returnToBoundaryCount(nums: number[]): number {
    let [ans, s] = [0, 0];
    for (const x of nums) {
        s += x;
        ans += s === 0 ? 1 : 0;
    }
    return ans;
}