无重复字符的最长子串
题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
🌰：
示例1：
输入: s = "abcabcbb"输出: 3解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例2：
输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例3：
输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
s 由英文字母、数字、符号和空格组成
解题过程⌨
- ❌，使用双指针，判断 i 与 j 指针下的元素是否相同，若不相同len+1，若相同 i +1。
- ⚠：这种做法忽略了在 j 指针遍历过程中遇到重复的问题以及字符串从头到尾无重复的情况
```javascript
const lengthOfLongestSubstring = function (s) {
let i = 0;
let j = i + 1;
let len = 0;
while (j < s.length) {
if (s[i] === s[j]) {
} j++; } return len; };len = j - i > len ? j - i : len;i++;
const len = lengthOfLongestSubstring(“pwwkew”);
2. ✔，使用str记录无重复字符串，j 指针遍历s字符串，若str中没有与s[j]相同的字符串，str += s[j]。若有相同的字符，那么记录下str的长度并且将重复前的字符串删除掉。
```javascript
const lengthOfLongestSubstring = function (s) {
if (s.length < 2) return s.length;
let len = 0;
let j = 1;
let str = s[0];
while (j < s.length) {
const index = str.indexOf(s[j]);
if (index !== -1) {
len = len < str.length ? str.length : len;
str = str.substring(index + 1, j);
}
str += s[j];
j++;
}
len = len < str.length ? str.length : len;
return len;
};
const len = lengthOfLongestSubstring("");
console.log(len);
通过删除字母匹配到字典里最长单词
题目：给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。 如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
🌰：
示例1：
输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"] 输出："apple"示例2：
输入：s = "abpcplea", dictionary = ["a","b","c"] 输出："a"解题过程⌨
- 排序+双指针对比
- 首先将dictionary进行排序，以长度为优先越长的字符串越靠前，当两个字符串的长度一致时，通过字符大小比较进行排序。
- 然后将排好序的dictionary进行循环找到合适的字符串，否则返回空字符串。
```javascript
const findLongestWord = (s, dictionary) => {
dictionary.sort((a, b) => b.length - a.length || (a < b && b.length === a.length ? -1 : 1))
for (let i = 0; i < dictionary.length; i++) {
let d = dictionary[i]
let sIndex = 0;
let dIndex = 0
while (sIndex < s.length && dIndex < d.length) {
} if (dIndex == d.length) {if (d[dIndex] === s[sIndex]) { dIndex++ } sIndex++
} } return ‘’ }return d
const response = findLongestWord(‘abpcplea’, [“ale”, “bpplee”, “apple”, “aonkey”, “plea”]) console.log(response)
2. [动态规划](https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/solution/tong-guo-shan-chu-zi-mu-pi-pei-dao-zi-di-at66/)
<a name="HpwCx"></a>
## 背向指针
<a name="KzFn2"></a>
### [验证回文串](https://leetcode.cn/problems/valid-palindrome/)
<a name="OpKF3"></a>
#### 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
- **说明：**本题中，我们将空字符串定义为有效的回文串。
<a name="rE6sZ"></a>
#### 🌰：
输入: “A man, a plan, a canal: Panama” 输出: true 解释：”amanaplanacanalpanama” 是回文串
```
输入: "race a car"
输出: false
解释："raceacar" 不是回文串
解题过程⌨
- 用正则匹配除去非数字与字母的字符。
- 获取中位字符，然后两两比对。
/** * @param {string} s * @return {boolean} */ var isPalindrome = function (s) { if (s.length === 0 || s.length === 1) return true let newStr = s.replace(/[^A-Za-z0-9]/g, '') const len = newStr.length; let left = 0; let right = 0; if (len % 2 === 0) { left = len / 2 - 1 right = len / 2 } else { let index = Math.floor(len / 2); left = index - 1; right = index + 1 } while (left > -1 && right < len) { if (newStr[left].toLocaleLowerCase() !== newStr[right].toLocaleLowerCase()) { return false } left--; right++; } return true };
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
🌰：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
输入：s = "cbbd"
输出："bb"
解题过程⌨
1. 中心扩展法
- 以每一个字符为中心，向两边扩展比较。
/** * @param {string} s * @return {string} */ var longestPalindrome = function (s) { if (s.length === 1) return s; let str = "" let maxStr = "" for (let cur = 1; cur < s.length; cur++) { str = s[cur]; let left = cur - 1, right = cur + 1; while (left > -1 && s[left] === s[cur]) { str = s[left] + str left--; } while (right < s.length && s[right] === s[cur]) { str += s[right] right++; } while (left > -1 && right < s.length && s[left] === s[right]) { str = s[left] + str + s[right]; left--; right++; } if (str.length > maxStr.length) { maxStr = str } } return maxStr };
回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
- 回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
🌰：
输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"解题过程⌨
1. 中心扩展法
因为具有不同开始位置或结束位置的子串，会被视作不同的子串。所以为了避免生成重复的子串，我们只能单项扩展。
/** * @param {string} s * @return {number} */ var countSubstrings = function (s) { if (s === "") return 0 let allLen = 0; for (let cur = 0; cur < s.length; cur++) { allLen++; let left = cur - 1 while (left > -1 && s[left] === s[cur]) { allLen++; left--; } let right = cur + 1 while (left > -1 && right < s.length && s[left] === s[right]) { left--; right++; allLen++ } } return allLen; };
相向指针
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
- 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
- 你可以按任意顺序返回答案。
🌰：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。解题过程⌨
1. 双指针法
```javascript /**
- @param {number[]} nums
- @param {number} target
- @return {number[]}
*/
var twoSum = function (nums, target) {
let i = 0;
while (i < nums.length) {
let otherNum = target - nums[i];
let j = nums.length - 1;
while (i < j) {
} i++ } };if (nums[j] === otherNum) { return [i, j]; } j--;<a name="d75Ar"></a> ##### 2. 使用map ```javascript /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function (nums, target) { const numMap = new Map(); for (let i = 0; i < nums.length; i++) { const otherNum = target - nums[i]; if (numMap.has(otherNum)) { return [i, numMap.get(otherNum)] } else { numMap.set(nums[i], i) } } };
两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和_ _index2。
- 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
-
🌰：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。解题过程⌨
1. 双指针法
指针指向的两个值之和与目标值相比较。
/** * @param {number[]} numbers * @param {number} target * @return {number[]} */ var twoSum = function (numbers, target) { let index1 = 0; let index2 = numbers.length - 1 while (index1 < index2) { const value = numbers[index1] + numbers[index2]; if (value === target) { return [++index1, ++index2] } else if (value > target) { index2-- } else { index1++ } } };
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
- 注意：答案中不可以包含重复的三元组。
🌰：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]输入：nums = [] 输出：[]输入：nums = [0] 输出：[]解题过程⌨
1. 排序+双指针
```javascript /**
- @param {number[]} nums
- @return {number[][]}
*/
var threeSum = function (nums) {
nums.sort((a, b) => a - b);
let result = []
for (let i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) break;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
} while (nums[i] === nums[i + 1]) {let total = nums[i] + nums[left] + nums[right] if (total === 0) { result.push([nums[i], nums[left], nums[right]]); // 去重 while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (total > 0) { right--; } else { left++; }
} } return result; }; ```i++
最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
- 返回这三个数的和。
- 假定每组输入只存在恰好一个解。
🌰：
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。输入：nums = [0,0,0], target = 1 输出：0解题过程⌨
1. 排序+双指针
/** * @param {number[]} nums * @param {number} target * @return {number} */ var threeSumClosest = function (nums, target) { nums.sort((a, b) => a - b) let gap = Infinity; let result = 0; for (let i = 0; i < nums.length - 2; i++) { let left = i + 1; let right = nums.length - 1; while (left < right) { let total = nums[i] + nums[left] + nums[right] let newGap = Math.abs(target - total); if (gap > newGap) { result = total gap = newGap; } if (target > total) { left++; } else { right--; } } while (nums[i] === nums[i + 1]) i++; } return result; };
若有收获，就点个赞吧
0 人点赞
