01.Two sum（两数之和）：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

解题思路：

1、创建一个map

2、for循环遍历nums数组

3、用target减nums[i]

4、检查map里有没有这个数：如果有则返回结果，如果没有则把num[i]当作key，i当作value放入map中

代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0; i < nums.length; i ++) {
        const complement = target - nums[i];
        if(map.has(complement)) {
            return [map.get(complement),i]
        }else {
            map.set(nums[i],i);
        }
    }
    return [];
};

02.Add Two Numbers（两数相加）：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

解题思路：

• 将其结果存在一个新的链表中
• 定义一个dummy，头结点
• 定义一个carry，用于存储某两个结点相加起来的值大于9的情况，如果大于，将个位数存入其中
• 定义一个curr，用于一个一个遍历新链表

代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode();//创建一个dummy头结点
    let curr = dummy;//用于一个一个遍历新链表
    let carry = 0;//用于记录是否要进位+1

    while(l1 != null || l2 != null) {
        let sum = 0;//记录和
        if(l1 != null) {
            sum += l1.val;//将结点的值加到sum中
            l1 = l1.next;//向后移动一位
        }
        if(l2 != null) {
            sum += l2.val;//将结点的值加到sum中
            l2 = l2.next;//向后移动一位
        }
        sum += carry;//加上carry的值
        curr.next = new ListNode(sum % 10);//新建一个结点，指向curr的后一位
        carry = Math.floor(sum / 10);//判断sum值是否大于等于10，如果大于，取个位，存入carry
        curr = curr.next;//curr向后移动一位
    }
    //判断，如果carry>0的，新建一个结点，
    if(carry > 0) {
        curr.next = new ListNode(carry);
    }
    //return 头结点的下一位
    return dummy.next;
};

03.无重复字符的最长字串：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路：

• sliding window
• 创建一个set

• 两个指针

  • 第一个指向字符串的开头
  • 第二个随着for循环遍历字符串
• 如果set里没有s[i]，说明目前为止还没有重复的字符，把s[i]添加到set里，然后更新最大不重复字符的数量
• 如果set里有s[i]，则从set里删除s[j]，并且递增j，再检查set里是否有s[i]，如此反复知道set里没有s[i]为止
• 直到遍历完整个字符串

代码：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // 创建一个set
    const set = new Set();
    // 定义两个指针，分别为i,j,maxLength为字串最大值
    let i = 0, j = 0, maxLength = 0;
    // 判断，如果字符串s为0，子串也为0
    if(s.length == 0) {
        return 0;
    }
    // i,j从第一个元素开始遍历
    for(i; i < s.length; i ++) {
        // 如果set中不存在s[i]这个值，将其添加
        if(!set.has(s[i])) {
            set.add(s[i]);
            maxLength = Math.max(maxLength,set.size);
        }else {
            while(set.has(s[i])) {
                // 删除s[j]的值，并将j向后移动
                set.delete(s[j]);
                j ++;
            }
            set.add(s[i]);
        }
    }
    return maxLength;
};

05.最长回文字串：

解题思路：

• 如果字符串长度小于2，直接返回原字符串
• 定义两个变量，一个start存储当前找到的最大回文字符串的起始位置，另一个maxLength记录字符串的长度（终止位置就是start+maxLength）
• 创建一个helper function，判断左边和右边是否越界，同时最左边的字符是否等于右边的字符，如果以上3个条件都满足，则判断是否需要更新回文字符串最大长度即最大字符串的起始位置，然后将left--，right++，继续判断，直到不满足三个条件之一
• 遍历字符串，每个位置调用helper function两遍，第一遍检查i-1,i+1，第二遍检查i,i+1

代码：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(s.length < 2) {
        return s;
    }

    let start = 0;
    let maxLength = 1;

    function expandAroundCenter(left,right) {
        while(left >= 0 && right < s.length && s[left] === s[right]) {
            if(right - left + 1 > maxLength) {
                maxLength = right - left + 1;
                start = left;
            }
            left --;
            right ++;
        }
    }
     for(let i = 0; i < s.length; i ++) {
         expandAroundCenter(i - 1, i + 1);
        expandAroundCenter(i, i + 1);
    }
    return s.substring(start,start + maxLength)
};

15.三数之和：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]
    

解题思路：

• 给数组排序
• 遍历数组，从0遍历到length-2
• 如果当前的数字等于前一个数字，则跳过这个数
• 如果数字不同，则设置start = i + 1，end = length - 1，查看i，start和end三个数的和比零大还是小，如果比0小，start++，如果比0大，end--，如果等于0，把这三个数加入到结果里
• 返回结果

代码：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const result = [];
    nums.sort(function(a,b) {
        return a - b;
    })
    
    for(let i = 0; i < nums.length - 2; i ++) {
        if(i === 0 || nums[i] !== nums[i - 1]) {
            let start = i + 1,end = nums.length - 1;
            while(start < end) {
                if(nums[i] + nums[start] + nums[end] === 0) {
                    result.push([nums[i],nums[start],nums[end]])
                    start ++;
                    end --;
                    while(start < end && nums[start] === nums[start - 1]) {
                        start ++;
                    }
                    while(start < end && nums[end] === nums[end + 1]) {
                        end --;
                    }
                }else if(nums[i] + nums[start] + nums[end] < 0) {
                    start ++;
                }else if(nums[i] + nums[start] + nums[end] > 0){
                    end --;
                }
            }
        }
    }
    return result;
};

21.合并两个有序链表：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

解体思路：

本题可以使用递归来解，将两个链表头部较小的一个与剩下的元素合并，并返回排好序的链表头，当两条链表中的一条为空时终止递归。

代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    if (list1 === null) {
        return list2
    }
    if(list2 === null) {
        return list1
    }
    if(list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next,list2)
        return list1;
    }else {
        list2.next = mergeTwoLists(list1,list2.next)
        return list2
    }
};

26.删除有序数组中的重复项：

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。

解题思路：

使用快慢指针来记录遍历的坐标。
开始时这两个指针都指向第一个数字
如果两个指针指的数字相同，则快指针向前走一步
如果不同，则两个指针都向前走一步
当快指针走完整个数组后，慢指针当前的坐标加 1 就是数组中不同数字的个数

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    const size = nums.length;
    if (size == 0) return 0;
    let slowP = 0;  //定义一个慢指针下标初始值0
    for(let fastP = 1; fastP < size; fastP ++) {    //遍历的时候，快指针从下标1开始
        if(nums[fastP] !== nums[slowP]) {   //如果快指针的值不等于慢指针的值。将慢指针向后移动，并且将快指针的值赋给慢指针
            slowP ++;
            nums[slowP] = nums[fastP];//将快指针的值赋给慢指针指向的位置
        }
    }
    return slowP + 1
};

66.加一：

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：
输入：digits = [0]
输出：[1]

解题思路：

这道题其实我们可以把它想象成小学生练习加法，只不过现在是固定的“加一”那么我们只需要考虑如何通过遍历来实现这个加法的过程就好了。

加法我们知道要从低位到高位进行运算，那么只需要对数组进行一次反向遍历即可。

伪代码：

for(int i = n - 1; i > - 1; i --) {
  内部逻辑
}

内部逻辑的话，其实有三种情况：

第一种情况是最简单的，我们只需将数组的最后一位进行+1 操作就好了

第二种情况稍微多了一个步骤：我们需要把个位的 carry 向前进一位并在计算是否有更多的进位

第三种其实和第二种是一样的操作，只是由于我们知道数组的长度是固定的，所以当我们遇到情况三的时候需要扩大数组的长度。我们只需要在结果数组前多加上一位就好了。

代码：

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    let carry = 1;  //初始化一个carry = 1
    // 对数组进行反向遍历
    for(let i = digits.length-1; i > -1; i --) {
        if(carry) {
            let sum = carry + digits[i];
            digits[i] = sum % 10;
            carry = sum > 9 ? 1 : 0;
        }
    }
    if(carry === 1) {
        digits.unshift(1)
    }
    return digits;
};

88.合并两个有序数组：

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

解题思路：

我们能只要从后往前比较，并从后往前插入即可
我们需要三个指针：
写指针 current， 用于记录当前填补到那个位置了
m 用于记录 nums1 数组处理到哪个元素了
n 用于记录 nums2 数组处理到哪个元素了

代码：

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let current = m + n -1  //定义一个指针，指向nums1的末尾
    while(current >= 0) {
        if(n === 0) return  //如果n的长度为0，没必要继续
        if(nums1[m - 1] > nums2[n - 1]) {
            nums1[current --] = nums1[--m]
        }else{
            nums1[current--] = nums2[--n]
        }
        if(m < 1) {
            nums1[current--] = nums2[--n]
            continue
        }
        if(n < 1) {
            nums1[current--] = nums1[--m]
            continue
        }
    }
};