> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/401-600/495.-ti-mo-gong-ji.md).

# 495. 提莫攻击

<https://leetcode-cn.com/problems/teemo-attacking/>

## 一、暴力（超时）

用一个count数组记录i秒中毒的总次数，遍历所有time序列，对`[time ... time+duration-1]`部分的count加一。

最后再看`count[i] != 0`的个数即可。`0 <= timeSeries[i], duration <= 10^7`，则i最大为2000000

```python
class Solution:
    def findPoisonedDuration(self, timeSeries, duration) -> int:
        count = [0] * 20000000
        for time in timeSeries:
            for i in range(duration):
                count[time + i] += 1
        res = 0
        for i in range(20000000):
            if count[i]:
                res += 1
        return res
```

## 二、暴力+优化

中毒时间会重叠，没必要重复计算。由于time序列非递减，因此直接遍历即可模拟时间正向，用now表示当前时间，每次now = time + duration。用count记录中毒时间总数

time与now只有两种情况：1）重叠，即time < now ；否则为2）不重叠。因为time序列非递减，不会有其他情况

重叠时count增量为duration - (now - time)，画图可知

不重叠增量直接为duration

```python
class Solution:
    def findPoisonedDuration(self, timeSeries, duration) -> int:
        now = 0
        count = 0
        for time in timeSeries:
            if time < now:
                count += duration - (now - time)
            else:
                count += duration
            now = time + duration
        return count
```