# 2022-06-01

## [438. Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/)

### Description

Given two strings `s` and `p`, return *an array of all the start indices of* `p`*'s anagrams in* `s`. You may return the answer in **any order**.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

**Example 1:**

```
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
```

**Example 2:**

```
Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
```

**Constraints:**

* `1 <= s.length, p.length <= 3 * 104`
* `s` and `p` consist of lowercase English letters.

### Solution

#### Approach #0

```go
func findAnagrams(s string, p string) (ans []int) {
    target, current := make([]int, 26), make([]int, 26)
    count := 0
    for _, ch := range p {
        target[ch-'a']++
    }
    for _, t := range target {
        if t != 0 {
            count++
        }
    }
    i, j, sig := 0, 0, 0
    for j < len(s) {
        in := s[j] - 'a'
        j++
        if target[in] > 0 {
            current[in]++
            if target[in] == current[in] {
                sig++
            }
        }
        for j-i >= len(p) {
            if sig == count {
                ans = append(ans, i)
            }
            out := s[i] - 'a'
            i++
            if target[out] > 0 {
                if current[out] == target[out] {
                    sig--
                }
                current[out]--
            }
        }
    }
    return ans
}
```

## [713. Subarray Product Less Than K](https://leetcode.com/problems/subarray-product-less-than-k/)

### Description

Given an array of integers `nums` and an integer `k`, return *the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than* `k`.

**Example 1:**

```
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
```

**Example 2:**

```
Input: nums = [1,2,3], k = 0
Output: 0
```

**Constraints:**

* `1 <= nums.length <= 3 * 10^4`
* `1 <= nums[i] <= 1000`
* `0 <= k <= 10^6`

### Solution

#### Approach #0

```go
func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
    cur := 1
    i, j := 0, 0
    for i < len(nums) {
        if j >= len(nums) {
            cur = 1
            i++
            j = i
            continue
        }
        in := nums[j]
        if cur*in < k {
            ans++
            cur = cur * in
            j++
        } else {
            cur = 1
            i++
            j = i
        }
    }
    return ans
}
```

#### Approach #1

```go
func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
    i, cur := 0, 1
    for j, num := range nums {
        cur *= num
        for ; i <= j && cur >= k; i++ {
            cur /= nums[i]
        }
        ans += j - i + 1
    }
    return
}
```

## [209. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/)

### Description

Given an array of positive integers `nums` and a positive integer `target`, return the minimal length of a **contiguous subarray** `[numsl, numsl+1, ..., numsr-1, numsr]` of which the sum is greater than or equal to `target`. If there is no such subarray, return `0` instead.

**Example 1:**

```
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
```

**Example 2:**

```
Input: target = 4, nums = [1,4,4]
Output: 1
```

**Example 3:**

```
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
```

**Constraints:**

* `1 <= target <= 10^9`
* `1 <= nums.length <= 10^5`
* `1 <= nums[i] <= 10^5`

**Follow up:** If you have figured out the `O(n)` solution, try coding another solution of which the time complexity is `O(n log(n))`.

### Solution

#### Approach #0

```go
func minSubArrayLen(target int, nums []int) (ans int) {
    ans = len(nums) + 1
    i, cur := 0, 0
    for j, num := range nums {
        cur += num
        for ; i <= j && cur >= target; i++ {
            if cur >= target {
                ans = min(ans, j-i+1)
            }
            cur -= nums[i]
        }
    }
    if ans == len(nums)+1 {
        ans = 0
    }
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
```