## [无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)

> 给定一个字符串 `s` ，请你找出其中不含有重复字符的 **最长子串** 的长度。
>
> **示例 1:**
>
> ```
> 输入: s = "abcabcbb"
> 输出: 3 
> 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
> ```
>
> **示例 2:**
>
> ```
> 输入: s = "bbbbb"
> 输出: 1
> 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
> ```
>
> **示例 3:**
>
> ```
> 输入: s = "pwwkew"
> 输出: 3
> 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
>      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
> ```

```js
var lengthOfLongestSubstring = function (s) {
  const counter = {}
  let ans = 0
  let left = 0

  for (let right in s) {
    counter[s[right]] = (counter[s[right]] || 0) + 1

    while (counter[s[right]] > 1) {
      counter[s[left]] -= 1
      left++
    }

    ans = Math.max(ans, right - left + 1)
  }

  return ans
}
```

时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符）。

## [长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum)

> 给定一个含有 `n` 个正整数的数组和一个正整数 `target` **。**
>
> 找出该数组中满足其总和大于等于 `target` 的长度最小的 **连续子数组** `[numsl, numsl+1, ..., numsr-1, numsr]` ，并返回其长度**。**如果不存在符合条件的子数组，返回 `0` 。
>
> **示例 1：**
>
> ```
> 输入：target = 7, nums = [2,3,1,2,4,3]
> 输出：2
> 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
> ```
>
> **示例 2：**
>
> ```
> 输入：target = 4, nums = [1,4,4]
> 输出：1
> ```
>
> **示例 3：**
>
> ```
> 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
> 输出：0
> ```

```js
var minSubArrayLen = function (target, nums) {
  let ans = Infinity
  let sum = 0
  let left = 0

  for (let right in nums) {
    sum += nums[right]

    while (sum >= target) {
      ans = Math.min(ans, right - left + 1)
      sum -= nums[left]
      left++
    }
  }

  return ans <= nums.length ? ans : 0
}
```

## [乘积小于 K 的子数组](https://leetcode.cn/problems/subarray-product-less-than-k)

> 给你一个整数数组 `nums` 和一个整数 `k` ，请你返回子数组内所有元素的乘积严格小于 `k` 的连续子数组的数目。
>
> **示例 1：**
>
> ```
> 输入：nums = [10,5,2,6], k = 100
> 输出：8
> 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
> 需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
> ```
>
> **示例 2：**
>
> ```
> 输入：nums = [1,2,3], k = 0
> 输出：0
> ```

```js
var numSubarrayProductLessThanK = function (nums, k) {
    if (k <= 1) return 0

    let left = 0
    let count = 0
    let product = 1

    for (let right = 0; right < nums.length; right++) {
        product *= nums[right]

        while (product >= k) {
            product /= nums[left]
            left++
        }

        count += right - left + 1
    }

    return count
};
```

## [最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring)

> 给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""` 。
>
> **注意：**
>
> - 对于 `t` 中重复字符，我们寻找的子字符串中该字符数量必须不少于 `t` 中该字符数量。
> - 如果 `s` 中存在这样的子串，我们保证它是唯一的答案。
>
> **示例 1：**
>
> ```
> 输入：s = "ADOBECODEBANC", t = "ABC"
> 输出："BANC"
> 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
> ```
>
> **示例 2：**
>
> ```
> 输入：s = "a", t = "a"
> 输出："a"
> 解释：整个字符串 s 是最小覆盖子串。
> ```
>
> **示例 3:**
>
> ```
> 输入: s = "a", t = "aa"
> 输出: ""
> 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
> 因此没有符合条件的子字符串，返回空字符串。
> ```

```js
function minWindow(s, t) {
  const charCount = new Map()
  let left = 0,
    minLen = Infinity,
    minWindowStart = 0,
    charsToMatch = t.length

  // 初始化字符计数
  for (const char of t) {
    charCount.set(char, (charCount.get(char) || 0) + 1)
  }

  for (let right = 0; right < s.length; right++) {
    const rightChar = s[right]

    if (charCount.has(rightChar) && charCount.get(rightChar) > 0) {
      charsToMatch--
    }

    charCount.set(rightChar, (charCount.get(rightChar) || 0) - 1)

    // 缩小左窗口
    while (charsToMatch === 0) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1
        minWindowStart = left
      }

      const leftChar = s[left]
      charCount.set(leftChar, (charCount.get(leftChar) || 0) + 1)

      if (charCount.get(leftChar) > 0) {
        charsToMatch++
      }

      left++
    }
  }

  return minLen === Infinity ? '' : s.substr(minWindowStart, minLen)
}
```


滑动窗口

## 排序+双指针

```js
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  nums.sort((a, b) => a - b)

  const ans = []
  const n = nums.length

  for (let i = 0; i < n - 2; i++) {
    // 当前元素不等于上一个元素
    if (i > 0 && nums[i] == nums[i - 1]) continue

    // 优化
    if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break
    if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue

    let j = i + 1
    let k = n - 1

    while (j < k) {
      const sum = nums[i] + nums[j] + nums[k]

      if (sum > 0) {
        k--
      } else if (sum < 0) {
        j++
      } else {
        ans.push([nums[i], nums[j], nums[k]])

        j++
        while (j < k && nums[j] === nums[j - 1]) {
          j++
        }

        k--
        while (j < k && nums[k] === nums[k + 1]) {
          k--
        }
      }
    }
  }

  return ans
}
```


三数之和

## 暴力枚举

```js
var twoSum = function (nums, target) {
  const n = nums.length

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (nums[i] + nums[j] === target && i !== j) {
        return [i, j]
      }
    }
  }
}
```

## 哈希表

```js
var twoSum = function (nums, target) {
  const map = new Map()

  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i]
    }
    map.set(nums[i], i)
  }
}
```


[无重复字符的最长子串](https://leetcode.cn/problems/longe

排序+双指针

暴力枚举

标题1

标题2

[WinPython 3.11.6.0更新日志][def]